短路径算法程解析
1概念
短路径：果图中某顶点（源点）达顶点（终点）路径止条找条路径路径边权值总（称路径长度）达
2短路径算法
（1）单源（某点余点）短路径—迪杰斯特拉（Dijkstra）算法
设带权图G(VE)顶点分两集合SVS中顶点集S已求出短路径终点集合（初始时S{s}）顶点集VS尚未求出短路径终点集合D[V]表示s出发S中顶点达v前短距离初始时顶点前短距离D图中sv边权值果sv没边D[v]∞D[s]0
短路径长度递增序逐VS中顶点加入S中直顶点加入S中止
Dijkstra算法时间复杂度O(N²)
道例题
例：图示批货物城市s发送城市t线条数字代表通条路费（单位：万元）运送批货物少需花费少元？
根算法构造表格Step步骤S已加入短路径顶点集合1~t加入顶点D[1]~D[t]出发点s改点短距离着顶点加入进行更新
Step
S
D[1]
D[2]
D[3]
D[4]
D[5]
D[6]
D[7]
D[8]
D[9]
D[t]
Step1
｛s｝
25
21
∞
∞
∞
∞
∞
∞
∞
∞
Step2
｛s2｝
25
41
46
∞
∞
∞
∞
∞
∞
Step3
｛s21｝
41
46
∞
∞
36
31
∞
∞
Step4
｛s218｝
41
46
∞
∞
36
64
∞
Step5
｛s2187｝
41
46
71
∞
64
∞
Step6
｛s21873｝
46
61
∞
64
∞
Step7
｛s218734｝
61
91
64
∞
Step8
｛s2187345｝
69
64
82
Step9
｛s21873459｝
69
81
Step10
｛s218734596｝
81
Step11
｛s218734596t｝
根表格知st花费少路径：s→2→1→8→7→3→4→5→9→6→t计需花费81万元
（2）顶点（意两点）间短路径—弗洛伊德（Floyd）算法
意节点i意节点j短路径2种直接ij二i干节点kj
假设D(ij)节点i节点j短路径距离节点k检查D(ik) + D(kj) < D(ij)否成立果成立证明ikj路径i直接j路径短设置D(ij) D(ik) + D(kj)遍历完节点kD(ij)中记录便ij短路径距离
Floyd算法时间复杂度O(N³)
面道例题：
例：明学准备ABCD四城市旅游四城市间分布路线图（路线数字两城市间距离箭头指单直接达）减少花费需提前解意两城市间短路程请根图示计算ABCD四城市中意两城市短路线
根算法构造矩阵D记录顶点间路径果两顶点间没直接相连设间距离穷矩阵P记录顶点间路径中中转点：P[a][c]表示ac短路径轨迹：a→b→c初始时表示未开始记1
D初始状态：
D
a
b
c
d
a
0
2
7
5
b
∞
0
3
∞
c
6
∞
0
1
d
4
∞
12
0
P初始状态：
P
a
b
c
d
a
1
1
1
1
b
1
1
1
1
c
1
1
1
1
d
1
1
1
1
1选择a中间点涉(ab)(ac)(ad)(ba)(ca)(da)6顶点更新意两点间距离(ab)路线仅1条ab距离2(ac)路线acabcadcabc＜ac＜adcabc距离5(ac)更新5(ad)路线adabcdacdad＜abcd＜acdad直接相连距离(ad)更新(ba)路线bcabcdabcda＜bcabada距离8(ba)更新8(ca)路线cacdacda＜cacda距离5(ca)更新5(da)路线dadcada＜dcada直接相连距离(da)更新更新D矩阵：
a
b
c
d
a
0
2
5
5
b
8
0
3
∞
c
5
∞
0
1
d
4
∞
12
0
更新P矩阵（红色数字代表两点间短距离需节点数蓝色数字0代表两点间直接相连距离）：
a
b
c
d
a
1
0
1
0
b
2
1
1
1
c
1
1
1
1
d
0
1
1
1
2选择b中间点述方法更新矩阵DP涉(ba)(bc)(bd)(ab)(cb)(db)(ab)(ba)已短（第1步已处理）需更新(bc)(bd)(cb)(db)(bc)路线bcbc3(bd)路线bcdbcadbcd＜dcadbcd4(bd)更新4(cb)路线cabcdabcdab＜cabcdab7(cb)更新7(db)路线dabdcabdab＜dcabdab6(db)更新6更新D矩阵：
D
a
b
c
d
a
0
2
5
5
b
8
0
3
4
c
5
7
0
1
d
4
6
12
0
更新P矩阵：
P
a
b
c
d
a
1
0
1
0
b
2
1
0
1
c
1
2
1
1
d
0
1
1
1
3选择c中间点述方法更新矩阵DP涉(ca)(cb)(cd)(ac)(bc)(dc)中(bc)已短(ac)(ca)(cb)已更新短剩(cd)(dc)未更新(cd)路线cdcadcd＜cadcd1(cd)更新(dc)路线dcdabcdacdabc＜dac＜dc(dc)更新9更新D矩阵：
D
a
b
c
d
a
0
2
5
5
b
8
0
3
4
c
5
7
0
1
d
4
6
9
0
更新P矩阵：
P
a
b
c
d
a
1
0
1
0
b
2
1
0
1
c
1
2
1
0
d
0
1
2
1
4d中间点述方法继续更新矩阵DP涉(da)(db)(dc)(ad)(bd)(cd)中(da)(ad)(cd)已短（第1步第3步已处理）(db)(dc)(bd)已更新短时意两点间短距离已完成D矩阵（数字表示两点间短距离）：
D
a
b
c
d
a
0
2
5
5
b
8
0
3
4
c
5
7
0
1
d
4
6
9
0
P矩阵（数字表示两点间短距离需节点数）：
P
a
b
c
d
a
1
0
1
0
b
2
1
0
1
c
1
2
1
0
d
0
1
2
1
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
1概念
短路径：果图中某顶点（源点）达顶点（终点）路径止条找条路径路径边权值总（称路径长度）达
2短路径算法
（1）单源（某点余点）短路径—迪杰斯特拉（Dijkstra）算法
设带权图G(VE)顶点分两集合SVS中顶点集S已求出短路径终点集合（初始时S{s}）顶点集VS尚未求出短路径终点集合D[V]表示s出发S中顶点达v前短距离初始时顶点前短距离D图中sv边权值果sv没边D[v]∞D[s]0
短路径长度递增序逐VS中顶点加入S中直顶点加入S中止
Dijkstra算法时间复杂度O(N²)
道例题
例：图示批货物城市s发送城市t线条数字代表通条路费（单位：万元）运送批货物少需花费少元？
根算法构造表格Step步骤S已加入短路径顶点集合1~t加入顶点D[1]~D[t]出发点s改点短距离着顶点加入进行更新
Step
S
D[1]
D[2]
D[3]
D[4]
D[5]
D[6]
D[7]
D[8]
D[9]
D[t]
Step1
｛s｝
25
21
∞
∞
∞
∞
∞
∞
∞
∞
Step2
｛s2｝
25
41
46
∞
∞
∞
∞
∞
∞
Step3
｛s21｝
41
46
∞
∞
36
31
∞
∞
Step4
｛s218｝
41
46
∞
∞
36
64
∞
Step5
｛s2187｝
41
46
71
∞
64
∞
Step6
｛s21873｝
46
61
∞
64
∞
Step7
｛s218734｝
61
91
64
∞
Step8
｛s2187345｝
69
64
82
Step9
｛s21873459｝
69
81
Step10
｛s218734596｝
81
Step11
｛s218734596t｝
根表格知st花费少路径：s→2→1→8→7→3→4→5→9→6→t计需花费81万元
（2）顶点（意两点）间短路径—弗洛伊德（Floyd）算法
意节点i意节点j短路径2种直接ij二i干节点kj
假设D(ij)节点i节点j短路径距离节点k检查D(ik) + D(kj) < D(ij)否成立果成立证明ikj路径i直接j路径短设置D(ij) D(ik) + D(kj)遍历完节点kD(ij)中记录便ij短路径距离
Floyd算法时间复杂度O(N³)
面道例题：
例：明学准备ABCD四城市旅游四城市间分布路线图（路线数字两城市间距离箭头指单直接达）减少花费需提前解意两城市间短路程请根图示计算ABCD四城市中意两城市短路线
根算法构造矩阵D记录顶点间路径果两顶点间没直接相连设间距离穷矩阵P记录顶点间路径中中转点：P[a][c]表示ac短路径轨迹：a→b→c初始时表示未开始记1
D初始状态：
D
a
b
c
d
a
0
2
7
5
b
∞
0
3
∞
c
6
∞
0
1
d
4
∞
12
0
P初始状态：
P
a
b
c
d
a
1
1
1
1
b
1
1
1
1
c
1
1
1
1
d
1
1
1
1
1选择a中间点涉(ab)(ac)(ad)(ba)(ca)(da)6顶点更新意两点间距离(ab)路线仅1条ab距离2(ac)路线acabcadcabc＜ac＜adcabc距离5(ac)更新5(ad)路线adabcdacdad＜abcd＜acdad直接相连距离(ad)更新(ba)路线bcabcdabcda＜bcabada距离8(ba)更新8(ca)路线cacdacda＜cacda距离5(ca)更新5(da)路线dadcada＜dcada直接相连距离(da)更新更新D矩阵：
a
b
c
d
a
0
2
5
5
b
8
0
3
∞
c
5
∞
0
1
d
4
∞
12
0
更新P矩阵（红色数字代表两点间短距离需节点数蓝色数字0代表两点间直接相连距离）：
a
b
c
d
a
1
0
1
0
b
2
1
1
1
c
1
1
1
1
d
0
1
1
1
2选择b中间点述方法更新矩阵DP涉(ba)(bc)(bd)(ab)(cb)(db)(ab)(ba)已短（第1步已处理）需更新(bc)(bd)(cb)(db)(bc)路线bcbc3(bd)路线bcdbcadbcd＜dcadbcd4(bd)更新4(cb)路线cabcdabcdab＜cabcdab7(cb)更新7(db)路线dabdcabdab＜dcabdab6(db)更新6更新D矩阵：
D
a
b
c
d
a
0
2
5
5
b
8
0
3
4
c
5
7
0
1
d
4
6
12
0
更新P矩阵：
P
a
b
c
d
a
1
0
1
0
b
2
1
0
1
c
1
2
1
1
d
0
1
1
1
3选择c中间点述方法更新矩阵DP涉(ca)(cb)(cd)(ac)(bc)(dc)中(bc)已短(ac)(ca)(cb)已更新短剩(cd)(dc)未更新(cd)路线cdcadcd＜cadcd1(cd)更新(dc)路线dcdabcdacdabc＜dac＜dc(dc)更新9更新D矩阵：
D
a
b
c
d
a
0
2
5
5
b
8
0
3
4
c
5
7
0
1
d
4
6
9
0
更新P矩阵：
P
a
b
c
d
a
1
0
1
0
b
2
1
0
1
c
1
2
1
0
d
0
1
2
1
4d中间点述方法继续更新矩阵DP涉(da)(db)(dc)(ad)(bd)(cd)中(da)(ad)(cd)已短（第1步第3步已处理）(db)(dc)(bd)已更新短时意两点间短距离已完成D矩阵（数字表示两点间短距离）：
D
a
b
c
d
a
0
2
5
5
b
8
0
3
4
c
5
7
0
1
d
4
6
9
0
P矩阵（数字表示两点间短距离需节点数）：
P
a
b
c
d
a
1
0
1
0
b
2
1
0
1
c
1
2
1
0
d
0
1
2
1
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档