最短路问题(Dijkstra算法).ppt

三、计算单源最短路问题（Dijkstra算法）分析：
设G=（V，E）是一个有向图，它的每一条边（U，V）∈Ｅ都有一个权W（U，V），在G中指定一个结点V0，要求把从V0到G的每一个结点Vj(VＪ∈Ｖ)的最短有向路找出来（或者指出不存在从V0到Vj的有向路，即V0不可达Vj）。这个问题即为单源最短路问题。解决单源最短路径的基本思想是把图中所有结点分为两组，每一个结点对应一个距离值
第一组：包括已确定最短路径的结点，结点对应的距离值是由v0到此结点的最短路径长度；
第二组：包括尚未确定最短路径的结点，结点对应的距离值是v0经由第一组结点（中间结点）至此结点的最短路径长度；
我们按最短路径长度递增的顺序把第二组的结点加到第一组中去，直至v0可达的所有结点都包含于第一组。在这个过程中，总保持从v0到第一组各结点的最短路径长度都不大于从v0至第二组任何结点的路径长度。具体作法是：
初始时v0进入第一组，v0的距离值为0；第二组包含其它所有结点，这些结点对应的距离值这样确定（设vi为第二组中的结点）

然后每次从第二组的结点中选一个其距离值为最小的结点vm加到第一组中。每往第一组加入一个结点vm，就要对第二组的各结点的距离值作一次修正（设vi为第二组的结点）：
若加进vm做中间结点使得v0至vi的路径长度更短（即vi的距离值>vm的距离值+Wmi），则要修改vi的距离（vi的距离值←vm的距离值+Wmi）。修改后再选距离值最小的一个结点加入到第一组中，…。如此进行下去，直至第一组囊括图的所有结点或再无可加入第一组的结点存在。显然，这种从第二组的结点中选距离值最小的结点扩展是一种贪心策略。设
n—图的结点数；
adj—有向图的相邻矩阵。其中
dist—最短路径集合。其中
dist[i]．pre—在v0至vi的最短路径上，vi的前趋结点序号；
dist[i]．length—v0至vI的最短路径长度，即vi的距离值；
（1≤i≤n）
Constn=图的结点数；
Type
path=record{路径集合的结点类型}
length：real；{距离值}
pre：0‥n；{前趋结点序号}
end；
var
adj：array[1‥n，1‥n]ofreal{相邻矩阵}
dist：array[1‥n]ofpath；{路径集合}
计算单源最短路径的过程如下：
fillchar(adj，sizeof(adj)，0)；{建立相邻矩阵adj}
fori←1tondo
forj←1tondo
if（i，j）∈Ethenadj[i，j]←wij
elseadj[i，j]←∞；
fori←1tondo{路径集合初始化}
begin
dist[i]．length←adj[v0，i]；
ifdist[i]．length<>∞
thendist[i]．pre←v0
elsedist[i]．pre←0；
end；{for}
adj[v0，v0]←1；{源结点v0进入第一组}
repeat
min←∞；u←0；
fori←1tondo{从第二组中找距离值最小的结点u}
算法结束时，沿着结点vi的pre指针回溯，便可确定v0至vi的最短路径：
procedureprint(i：integer)；
begin
ifi=v0then输出结点v0
elsebegin
print(dist[i]．pre)；
输出结点i和v0至vi的最短路径长度dist[i]．length；
end；{else}
end；{print}
显然递归调用print[1]，…，print[n]后，可得知v0至所有结点的最短路径。由此得出主程序：
输入城镇数n；
输入出发城镇序号v0；
输入城镇间的距离矩阵w；
计算单源最短路径方案dist；
fori←1tondo{枚举除v0外的其它城镇}
begin
if(i<>v0)and(dist[i]．length<>∞){若城镇i与城镇v0间有通路，则输出它们之间的最短距离和路径方案}
thenbeginwrtiln(dist[i]．length)；print(i)；end；{then}
wrteln；
end；{for}

位图算法分析设
const
maxn=150；{位图的规模}
move：array[1..4，1..2]ofinteger=((1，0)，(0，1)，(-1，0)，(0，-1))；{四个方向所对应的水平竖直增量}
var
used：array[1..maxn，1..maxn]ofboolean；{像素已访问标志}
list：array[1..maxn*maxn，1..2]ofinteger；{list[i]为第i个源点(白像素)的坐标}
map ：array[1..maxn，1..maxn]ofinteger；{map[i，j]为（i，