面试找出最短路径

[Jhonson]

题目描述如图链接

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

Talk is cheap,show your code!

[classyk]

这个不就是 Astar 算法吗

[baiihcy]

BFS 就能实现了吧

[Jhonson]

@classyk 谢谢你，这个图算法真有意思，我在看相关资料了！

[Jhonson]

@baiihcy 应该是没有问题的，BFS 和 DFS 感觉是万能的呀- -

[LawlietZ]

裸 dijksta 啊 超级简单。。。哪个公司的面试啊。。。

[ayyll]

@baiihcy bfs 解单源最短路吧。。他这任意两点 明显是多源 bfs 确定不会被询问哭？ 所以 Floyd 吧

[ayyll]

@LawlietZ 难道不是裸 Floyd。。。任意两点 dij 是一点到任意点吧。。

[cbais7890]

推荐一个可视化: https://qiao.github.io/PathFinding.js/visual/

[takato]

@classyk

@Jhonson

A*无法保证全局最优

[Linxing]

@cbais7890 感谢 很形象

[Parallel]

题目描述的表示图的方式叫，邻接矩阵。针对这个题目，对应不同的查询需求，可以扯的有很多。
以下，n 为顶点数，e 为边数。
O(n^3) Floyd
O(n^2) Dijkstra
O(n*e) Bellman-ford
O(e) SPFA

[ballshapesdsd]

你们都审题了没有啊，怎么迪杰斯特拉都出来了

[LawlietZ]

@ayyll 我觉得是表述问题，一般不会深问多源最短路

[Parallel]

@ballshapesdsd 哦，点开链接才看到完整的题目，理解题目有误。

[LawlietZ]

@Parallel SPFA 是 ke，常数 k 不能省略

[takato]

@ballshapesdsd 似乎好多人理解成了邻接矩阵。。。
其实是张迷宫图。。。

[wannafly]

@takato 当然可以。取决于你的 heuristic function 怎么取，比如退化成最简单的迷宫算法。

[HiJ2017]

这是很经典的数据结构题,当时教材上给了 BFS 和 DFS 两种解法
<数据结构教程>--李春葆

[takato]

@wannafly A×这个优化是要建立在去掉“最”的情况下的，即如果你只要一个局部最优。

[takato]

@wannafly fix "A*"..被输入法替换了符号。。