图论动画-Dial算法

null15.082 和 6.855J 15.082 和 6.855J 使用简单桶的Dijkstra 算法 (也是闻名的Dial 算法)例子例子123456242 1342 32初始化距离标号选择带有最小临时距离标号的结点1初始化桶更新步更新步23456242 1342 322401123选择最小临时标号选择最小临时标号13456242 1342 32240245623通过从最左端的桶开始且向右扫描直到找到非空桶，来寻找最小值.更新步更新步123456242 1342 3224643045623345选择最小临时标号选择最小临时标号12456242 1342 322364036345通过从最左端的桶开始且向右扫描直到找到非空桶，来寻找最小值.更新更新12456242 1342 320323646345选择最小临时标号选择最小临时标号1246242 1342 320323645645更新 更新 1246242 1342 32032364566456选择最小临时标号选择最小临时标号126242 1342 3203236456446更新更新126242 1342 3203236456446选择最小临时标号选择最小临时标号12242 1342 3203236456466没有可更新的了算法结束算法结束12242 1342 320323645646所有结点都保持不变了前驱形成一棵树通过回溯前驱，可以找到从结点 1 到结点 6 的最短路径