面试找出最短路径

[Jhonson]

题目描述如图链接

题目大意就是给定一个 n x m 的矩阵，矩阵只含 0 或者 1，其中 0 代表连通，1 代表阻断，给定任意矩阵内两点 A B 坐标，要求找出 A->B 的最短路径（假设是可达的），大家有什么好的思路吗，多多益善，谢谢了。(如果描述不清楚，还请提出。)

Talk is cheap,show your code!

[silhouette]

floyd，模板题

[yanaraika]

@LawlietZ 8102 年了还 SPFA O(kE)……搞个网格图就退化到 O(ve)了

[yanaraika]

@Parallel 别用 SPFA 了……随便搞搞就卡成 O(ne)了

[wizardforcel]

floyd 有点浪费了，它最后就要 distance[A][B]

[takato]

@wannafly 问题是如果退化了以后，状态数还是和 DFS,BFS 一样，那么这个 function 在这个例子中的意义在哪里？
当然我可以理解想做一个 Universal Algorithm/Model 的决心，但是也别忘了 overfit 的存在。

即如果只是要个 local minimum，你说的就是比较好的方法，但是源问题不是这样定义的。

[JohnSmith]

动规问题 刚做过

[JohnSmith]

@JohnSmith 审错题了

[IceCola1]

对于的矩阵转换为图，如果只是 0，1 的话，深搜或者广搜都可以，时间复杂度都是 OV2,如果有权重的话，用 Dijkstra,时间复杂度，OV2，如果有负权重的话，bellman-ford 算法 O(VE)，如果所有点对都要输出的话，floyd 算法 O(V3)

[Rico]

可以参考我之前写的 A*算法，有动图 https://hogwartsrico.github.io/2016/03/11/AStarPathFinding/

[lsmgeb89]

bfs

[crab]

@Rico 页面点章节都空白

[Mirana]

dp

[jedihy]

这种题目就真的不 show code 了，BFS 送分题。

[jedihy]

@Rico 你的博客 chrome 只看得到提纲和地下的 footer。

[wolegequ]

还 talk is cheap 😅

[jssyxzy]

算法自己复习。

[laxenade]

leetcode 64 的变种？

[xiadong1994]

这种路径长度都相同的题，用不着 dijkstra，单纯的 BFS。另外面试一般不会考 Floyd 吧……

[thedrwu]

看需要查询几次。 是否需要“最”优解。 如果只考虑短时间内能简单实现的解法：

若查询一次可以如楼上用广搜。

若查询多次，整张 n×m 表一遍一遍的扫（递推），假设点 a->点 z, 每扫一遍更新上一歩的解(a->b->z 中的 b)和最优路径和歩数， 直到收敛。 空间只需要 O(n×m)。

[wannafly]

@takato 只要能保证 heuristic cost 算出来小于等于实际的 cost，那么就能保证得到的解是全局最优解。这种情况下也是能减少所要搜索的状态数量的。