面试找出最短路径

2018 年 6 月 27 日
 Jhonson

题目描述如图链接

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

Talk is cheap,show your code!

11363 次点击
所在节点    程序员
75 条回复
classyk
2018 年 6 月 27 日
这个不就是 Astar 算法吗
baiihcy
2018 年 6 月 27 日
BFS 就能实现了吧
Jhonson
2018 年 6 月 27 日
@classyk 谢谢你，这个图算法真有意思，我在看相关资料了！
Jhonson
2018 年 6 月 27 日
@baiihcy 应该是没有问题的，BFS 和 DFS 感觉是万能的呀- -
LawlietZ
2018 年 6 月 27 日
裸 dijksta 啊 超级简单。。。哪个公司的面试啊。。。
ayyll
2018 年 6 月 27 日
@baiihcy bfs 解单源最短路吧。。他这任意两点 明显是多源 bfs 确定不会被询问哭？ 所以 Floyd 吧
ayyll
2018 年 6 月 27 日
@LawlietZ 难道不是裸 Floyd。。。任意两点 dij 是一点到任意点吧。。
cbais7890
2018 年 6 月 27 日
推荐一个可视化: https://qiao.github.io/PathFinding.js/visual/
takato
2018 年 6 月 27 日
@classyk

@Jhonson

A*无法保证全局最优
Linxing
2018 年 6 月 27 日
@cbais7890 感谢 很形象
Parallel
2018 年 6 月 27 日
题目描述的表示图的方式叫，邻接矩阵。针对这个题目，对应不同的查询需求，可以扯的有很多。
以下，n 为顶点数，e 为边数。
O(n^3) Floyd
O(n^2) Dijkstra
O(n*e) Bellman-ford
O(e) SPFA
ballshapesdsd
2018 年 6 月 27 日
你们都审题了没有啊，怎么迪杰斯特拉都出来了
LawlietZ
2018 年 6 月 27 日
@ayyll 我觉得是表述问题，一般不会深问多源最短路
Parallel
2018 年 6 月 27 日
@ballshapesdsd 哦，点开链接才看到完整的题目，理解题目有误。
LawlietZ
2018 年 6 月 27 日
@Parallel SPFA 是 ke，常数 k 不能省略
takato
2018 年 6 月 27 日
@ballshapesdsd 似乎好多人理解成了邻接矩阵。。。
其实是张迷宫图。。。
wannafly
2018 年 6 月 27 日
@takato 当然可以。取决于你的 heuristic function 怎么取，比如退化成最简单的迷宫算法。
HiJ2017
2018 年 6 月 27 日
这是很经典的数据结构题,当时教材上给了 BFS 和 DFS 两种解法
<数据结构教程>--李春葆
takato
2018 年 6 月 27 日
@wannafly A×这个优化是要建立在去掉“最”的情况下的，即如果你只要一个局部最优。
takato
2018 年 6 月 27 日
@wannafly fix "A*"..被输入法替换了符号。。

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://study.congcong.us/t/466369

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX