面试找出最短路径

[Jhonson]

题目描述如图链接

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

Talk is cheap,show your code!

[hackpro]

@cbais7890 #8 为啥我拽不动绿色方块 也没找到红色方块？
Win10 64bit Chrome 67.0

[zzj0311]

就是个 A*，哪那么多问题。。

[stargazer]

@Jhonson 写啥，说了大体思路，不行，必须手写，写毛啊，前边各种问题已经问了一个多小时了，再写俩小时代码？

[lzhCoooder]

dijksta 和 A*都可以啊，选哪个看实际情况，面试的话把这两个算法都说出来没毛病

[salamanderMH]

写文章记录过
https://segmentfault.com/a/1190000010285088

[yao978318542]

https://anvaka.github.io/ngraph.path.demo/ 你可以看看这个

[mogami18]

floyd

[zke1e]

dijkstra 啊

[maggch]

这题边权都是 1,最优就是 BFS 了

[maggch]

Dijkstra 带 log ,Floyd 复杂度 n^3,做这题时间复杂度都非常的不优秀

[cbais7890]

@hackpro #61
貌似大家都没问题, 如果要排除插件问题, 用隐身模式试试 ?

[LawlietZ]

@yanaraika 与几几年有什么关系呢，退化不退化还是看数据吧，acm 里面不还是很多去使用 spfa 去做最短路的题。。当然我个人更倾向用队列优化的 Dij，SPFA 的 k 值是由算法中点的入队出队次数决定的，一般还是不容易直接降到 ne 吧

[classyk]

@takato 实际应用中 A 星算法就是最佳选择，除非你地图实在太小了，不需要注意任何效率问题了

[takato]

@classyk 不不不，现实问题都不是全局最优问题，求全局最优用 A*基本就是.....那啥....

建议打好基础.

[hobochen]

@maggch fib 堆好像可以去掉 log ？