听ghost讲那最短路的事情之dijkstra算法

图论中的最短路算法,应该是每个进入图论的oier的入门课吧,虽然可能讲一节这个多此一举,但(为了凑数)还是说一说吧~

名称

dijkstra算法

属性

单源最短路算法、巨R眼镜(喂喂喂好像稍稍跑偏了啊……)

来历

在很久很久以前,互联网的规模还没发展到惊天地泣鬼神的时候,网络上的路由器依照静态路由表计算从一个节点(或网络)到另一个节点(或网络)的最短传包路径,就是用的dijkstra算法

思想

首先根据图的情况建立邻接矩阵,从出发点到各个节点的路径都有一个权值(没有道路直接相连置为+∞)如下图: 啊咧图片好像没有加载出来

可建立邻接矩阵如下:

0   11  53  +
11  0   1   +
53  1   0   6
+  +  6   0

接下来,寻找从节点1出发到各个其他节点的最短直连路,也就是从上面矩阵的第一行中找出(除了从一到一的那个0权回路以外的)最小值,当然,根据我超人的智慧已经提前你们找出来了,就是那个53!哇嘎嘎嘎……咳咳,言归正传,是那个从节点1到节点2的权为11的路径,此时,第一轮路径优化开始:把11那条路练的节点2当做从节点1侵略其他节点的“中继站”,看看“是从节点1直接到节点3权值(53)小呢”还是“以2为中继站倒一趟车再到节点3权值(12)小呢?”当然是12<53,现在把第一行第三列的53更新为12,也就是现在已知的从节点1到节点3的道路权值最小的是12;然后看能不能同理更新节点1到节点4的权值,不过可惜啊,两条路径都是正无穷权值,到节点4的权值没法更新了。接下来是第一轮路径优化的善后处理:把节点2置一个“已使用”标志,这样下一轮找中继站的时候就不会再找到节点2,这样的路径优化进行三遍后,临街矩阵的第一行就变了样子,也就是列出了从节点1到各个节点的最小权值:

0 11 12 18

这就是求最小权值的问题,如果要求再提高一点,想要求最短权值路径,就要在路径优化的时候多记一个数据,就是从节点1到被更新的点本轮使用的“中继站”是哪个节点,等输出的时候递归输出即可。

点评

dijkstra可谓图论最短路问题中资格最老也是最眼镜娘(循规蹈矩)的算法了,整个算法透着一股明显的贪心气息,是每个学习图论的oier居家旅行必备良方……

时间复杂度

O(n^2)因为路径优化进行了n-1(n是节点数)次,每次检查了n-1个节点是否能被更新路径。


Written by Zhang, Zijian in 马放南山 on 二 01 二月 2011. Tags: NOIP, 最短路, 算法, Dijkstra,

Comments

comments powered by Disqus