本文借鑒于張廣河教授主編的《數(shù)據(jù)結(jié)構(gòu)》，對其中的代碼進(jìn)行了完善。
從某源點(diǎn)到其余各頂點(diǎn)的最短路徑
Dijkstra算法可用于求解圖中某源點(diǎn)到其余各頂點(diǎn)的最短路徑。假設(shè)G=｛V，｛E｝｝是含有n個(gè)頂點(diǎn)的有向圖，以該圖中頂點(diǎn)v為源點(diǎn)，使用Dijkstra算法求頂點(diǎn)v到圖中其余各頂點(diǎn)的最短路徑的基本思想如下：
- 使用集合S記錄已求得最短路徑的終點(diǎn)，初始時(shí)S={v}。
- 選擇一條長度最小的最短路徑，該路徑的終點(diǎn)w屬于V-S，將w并入S，并將該最短路徑的長度記為Dw。
-
對于V-S中任一頂點(diǎn)是s，將源點(diǎn)到頂點(diǎn)s的最短路徑長度記為Ds，并將頂點(diǎn)w到頂點(diǎn)s的弧的權(quán)值記為Dws，若Dw+Dws
則將源點(diǎn)到頂點(diǎn)s的最短路徑長度修改為Dw+Ds=ws。 -
重復(fù)執(zhí)行2和3，知道S=V。
為了實(shí)現(xiàn)算法， - 使用鄰接矩陣Arcs存儲有向網(wǎng)，當(dāng)i=j時(shí)，Arcs[i][j]=0；當(dāng)i!=j時(shí)，若下標(biāo)為i的頂點(diǎn)到下標(biāo)為j的頂點(diǎn)有弧且弧的權(quán)值為w，則Arcs[i][j]=w，否則Arcs[i][j]=float(‘inf’)即無窮大。
- 使用Dist存儲源點(diǎn)到每一個(gè)終點(diǎn)的最短路徑長度。
- 使用列表Path存儲每一條最短路徑中倒數(shù)第二個(gè)頂點(diǎn)的下標(biāo)。
- 使用flag記錄每一個(gè)頂點(diǎn)是否已經(jīng)求得最短路徑，在思想中即是判斷頂點(diǎn)是屬于V集合，還是屬于V-S集合。
代碼實(shí)現(xiàn)
#構(gòu)造有向圖Graph
class
Graph
:
def
__init__
(
self
,
graph
,
labels
)
:
#labels為標(biāo)點(diǎn)名稱
self
.
Arcs
=
graph
self
.
VertexNum
=
graph
.
shape
[
0
]
self
.
labels
=
labels
def
Dijkstra
(
self
,
Vertex
,
EndNode
)
:
#Vertex為源點(diǎn)，EndNode為終點(diǎn)
Dist
=
[
[
]
for
i
in
range
(
self
.
VertexNum
)
]
#存儲源點(diǎn)到每一個(gè)終點(diǎn)的最短路徑的長度
Path
=
[
[
]
for
i
in
range
(
self
.
VertexNum
)
]
#存儲每一條最短路徑中倒數(shù)第二個(gè)頂點(diǎn)的下標(biāo)
flag
=
[
[
]
for
i
in
range
(
self
.
VertexNum
)
]
#記錄每一個(gè)頂點(diǎn)是否求得最短路徑
index
=
0
#初始化
while
index
<
self
.
VertexNum
:
Dist
[
index
]
=
self
.
Arcs
[
Vertex
]
[
index
]
flag
[
index
]
=
0
if
self
.
Arcs
[
Vertex
]
[
index
]
<
float
(
'inf'
)
:
#正無窮
Path
[
index
]
=
Vertex
else
:
Path
[
index
]
=
-
1
#表示從頂點(diǎn)Vertex到index無路徑
index
+=
1
flag
[
Vertex
]
=
1
Path
[
Vertex
]
=
0
Dist
[
Vertex
]
=
0
index
=
1
while
index
<
self
.
VertexNum
:
MinDist
=
float
(
'inf'
)
j
=
0
while
j
<
self
.
VertexNum
:
if
flag
[
j
]
==
0
and
Dist
[
j
]
<
MinDist
:
tVertex
=
j
#tVertex為目前從V-S集合中找出的距離源點(diǎn)Vertex最斷路徑的頂點(diǎn)
MinDist
=
Dist
[
j
]
j
+=
1
flag
[
tVertex
]
=
1
EndVertex
=
0
MinDist
=
float
(
'inf'
)
#表示無窮大，若兩點(diǎn)間的距離小于MinDist說明兩點(diǎn)間有路徑
#更新Dist列表，符合思想中第三條
while
EndVertex
<
self
.
VertexNum
:
if
flag
[
EndVertex
]
==
0
:
if
self
.
Arcs
[
tVertex
]
[
EndVertex
]
<
MinDist
and
Dist
[
tVertex
]
+
self
.
Arcs
[
tVertex
]
[
EndVertex
]
<
Dist
[
EndVertex
]
:
Dist
[
EndVertex
]
=
Dist
[
tVertex
]
+
self
.
Arcs
[
tVertex
]
[
EndVertex
]
Path
[
EndVertex
]
=
tVertex
EndVertex
+=
1
index
+=
1
vertex_endnode_path
=
[
]
#存儲從源點(diǎn)到終點(diǎn)的最短路徑
return
Dist
[
EndNode
]
,
start_end_Path
(
Path
,
Vertex
,
EndNode
,
vertex_endnode_path
)
#根據(jù)本文上述定義的Path遞歸求路徑
def
start_end_Path
(
Path
,
start
,
endnode
,
path
)
:
if
start
==
endnode
:
path
.
append
(
start
)
else
:
path
.
append
(
endnode
)
start_end_Path
(
Path
,
start
,
Path
[
endnode
]
,
path
)
return
path
if
__name__
==
'__main__'
:
#float('inf')表示無窮
graph
=
np
.
array
(
[
[
0
,
6
,
5
,
float
(
'inf'
)
,
float
(
'inf'
)
,
float
(
'inf'
)
]
,
[
float
(
'inf'
)
,
0
,
2
,
8
,
float
(
'inf'
)
,
float
(
'inf'
)
]
,
[
float
(
'inf'
)
,
float
(
'inf'
)
,
0
,
float
(
'inf'
)
,
3
,
float
(
'inf'
)
]
,
[
float
(
'inf'
)
,
float
(
'inf'
)
,
7
,
0
,
float
(
'inf'
)
,
9
]
,
[
float
(
'inf'
)
,
float
(
'inf'
)
,
float
(
'inf'
)
,
float
(
'inf'
)
,
0
,
9
]
,
[
float
(
'inf'
)
,
float
(
'inf'
)
,
float
(
'inf'
)
,
float
(
'inf'
)
,
0
]
]
)
G
=
Graph
(
graph
,
labels
=
[
'a'
,
'b'
,
'c'
,
'd'
,
'e'
,
'f'
]
)
start
=
input
(
'請輸入源點(diǎn)'
)
endnode
=
input
(
'請輸入終點(diǎn)'
)
dist
,
path
=
Dijkstra
(
G
,
G
.
labels
.
index
(
start
)
,
G
.
labels
.
index
(
endnode
)
)
Path
=
[
]
for
i
in
range
(
len
(
path
)
)
:
Path
.
append
(
G
.
labels
[
path
[
len
(
path
)
-
1
-
i
]
]
)
print
(
'從頂點(diǎn){}到頂點(diǎn){}的最短路徑為：\n{}\n最短路徑長度為：{}'
.
format
(
start
,
endnode
,
Path
,
dist
)
)
輸出結(jié)果如下：
請輸入源點(diǎn)
a
請輸入終點(diǎn)
f
從頂點(diǎn)a到頂點(diǎn)f的最短路徑為：
['a', 'c', 'e', 'f']
最短路徑長度為：17
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
