问一个关于最短路径的Dijkstra算法的问题

streethacker

我对Dijkstra算法没怎么理解清楚，请教一下大家。最好能分步骤给解释一下，谢谢。

timothyqiu

分步骤给解释一下：http://zh.wikipedia.org/wiki/Dijkstra算法

mci2004

Dijkstra算法正确性和核心都是基于一个假设：

假设 IN---->OUT 最短的路径是 IN-->A--->B--->C....--->OUT。

那么在这个最短路径上，从IN到每个顶点的距离都是最短的，例如：从IN到达C顶点的最短距离一定是 IN-->A-->B-->C。怎么证明，相信你知道的对吧？

IN做为起点，这样一步一步的迭代就能求得最短路径了。IN---A---B

还有，如果两点之间不可达，则将这两点之间的距离设置为 INFINITE。

streethacker

多谢
回复 2# timothyqiu


   

streethacker

多谢，看了一下楼上的动态图，又看了一下你的解释，现在明白了
回复 3# mci2004


   

Ager

如果楼主要在考试前，做关于“单源最短路径Dijkstra算法“的“小抄”的话，就以下八个字：

膨胀 -> 触碰 -> 比较 -> 更新 -> 膨胀 -> ....

Ager

starwing83 发表于 2013-01-13 19:51
回复 6# Ager

还有一种特殊的cheatsheet，直接翻译就是作弊表，而且做成非常言简意赅的表格形状，十分利于打印出来裁剪~~

说得没错！

一些台湾的IT书籍，也喜欢在封面的勒口（Flap）处，印上这种Cheatsheet。

还有，一些高级的编程式计算器，也会在保护盖内侧，印上Cheatsheet。

呵呵。。。