分享下自己对dijkstra 算法 的理解

广度有限结合贪心思想。解决图中从固定源节点到所有节点的最便宜走法。。

具体看pdf....

英语很不不行。就猜中文看吧。。。。

请给点大米。。。。

实话实说，我觉得这边文章写的不错。。。。。

唯一的缺点就是楼主太谦虚了。

https://zany-fluorine-852.notion ... b61bce463cb0e4a1183

学dijkstra算法的时候，我被一个很直观的visualization洗过脑，然后就再也忘不掉了。

想象面前平铺着一张渔网，我们要做的就是拎住渔网上的一个节点，慢慢把整张渔网拉起来。渔网上的节点会一个一个地脱离地面，这个过程就是dijkstra算法。

dijk本质就是每次贪心算出一个点的最短距离，循环n次

Dijkstra 算法的另一个名字叫Uniform Cost Search 。在你脑海中想象，从起始点S开始，哪些点是可以到达的，并且到达他们的距离是多少，取最小的那个出来（叫它点P），这个距离就是到这个点的最短路径，然后我们看看从这个点出去又可以到达哪些其他的点，到这些点的距离就是到P的距离加上对应边的距离。然后从所有这些可到达的点（记得包括上一轮的那些点哦）再取（距离）最小的那个出来，然后重复。
代码也好实现，iterarive的，用一个priority queue，按照上面的方法把这些点（以及的对应的到这些点的距离）放在这个queue里，每次取最小的出来。
同理，bfs, dfs, heuristic, A*都可以同样实现，唯一区别就是priory queue 是怎么确定priority 的：
Bfs对应FIFO quque
Dfs对应FILO queue
UCS对应用cumulative distance from S的priority queue
A*对应用 cumulative distance from S + estimate distance to G (target node)

CS188（Berkeley的本科AI课）的一开始就讲的这个，因为怎样Search for a (shortest) path是很多intelligent agent的一个核心步骤（想想我们每天是不是经常问自己： 从宿舍怎么走到教学楼最快，怎么最快修完专业所需所有课程，怎么花最少钱做成xxx)。更广义一点就是说怎么样去搜索一个optimization问题的解。
你甚至可以说，AI的最终解决朴实无华，就是有足够的算计去搜索一个最短路径in一个巨巨巨巨大的空间（当然我是不太了解也不太认同的，我认同的是每次算计有大提升效果也明显地会有大提升）。

欢迎有insight的朋友补充。

楼上这语言的简介和清晰的思维，感觉是个高手。

这个PDF有办法下载么？

不是pdf, 是notion内嵌pdf,,,上传pdf会消耗硬币。。。。

Xiangu 发表于 2023-01-07 01:04:45
Dijkstra 算法的另一个名字叫Uniform Cost Search 。在你脑海中想象，从起始点S开始，哪些点是可以到达的，并且到达他们的距离是多少，取最小的那个出来（叫它点P），这个距离就是到

好生羡慕此生能坐在白克礼的计算机的课堂

Xiangu 发表于 2023-01-07 01:04:45
Dijkstra 算法的另一个名字叫Uniform Cost Search 。在你脑海中想象，从起始点S开始，哪些点是可以到达的，并且到达他们的距离是多少，取最小的那个出来（叫它点P），这个距离就是到

确实如此，本质都是PFS（priority first search），清华大学邓俊辉老师讲的也很不错。

是辣本教材不。