文章目錄
- 前言
- 1. 創建圖
- 2. 問題來源
- 3. Dijkstra演算法
- 4. Floyd演算法
- 5. 代碼測驗
前言
??本篇章主要介紹圖的最短路徑問題，包括Dijkstra演算法和Floyd演算法，并用Python代碼實作，
1. 創建圖
??在開始之前，我們先創建一個圖，使用鄰接矩陣表示有向網：
class Graph(object):
"""
以鄰接矩陣為存盤結構創建有向網
"""
def __init__(self, kind):
# 圖的型別: 無向圖, 有向圖, 無向網, 有向網
# kind: Undigraph, Digraph, Undinetwork, Dinetwork,
self.kind = kind
# 頂點表
self.vertexs = []
# 邊表, 即鄰接矩陣, 是個二維的
self.arcs = []
# 當前頂點數
self.vexnum = 0
# 當前邊(弧)數
self.arcnum = 0
def CreateGraph(self, vertex_list, edge_list):
"""
創建圖
:param vertex_list: 頂點串列
:param edge_list: 邊串列
:return:
"""
self.vexnum = len(vertex_list)
self.arcnum = len(edge_list)
for vertex in vertex_list:
vertex = Vertex(vertex)
# 頂點串列
self.vertexs.append(vertex)
# 鄰接矩陣, 初始化為無窮
self.arcs.append([float('inf')] * self.vexnum)
for edge in edge_list:
ivertex = self.LocateVertex(edge[0])
jvertex = self.LocateVertex(edge[1])
weight = edge[2]
self.InsertArc(ivertex, jvertex, weight)
def LocateVertex(self, vertex):
"""
定位頂點在鄰接表中的位置
:param vertex:
:return:
"""
index = 0
while index < self.vexnum:
if self.vertexs[index].data == vertex:
return index
else:
index += 1
def InsertArc(self, ivertex, jvertex, weight):
"""
創建鄰接矩陣
:param ivertex:
:param jvertex:
:param weight:
:return:
"""
if self.kind == 'Dinetwork':
self.arcs[ivertex][jvertex] = weight
??有關鄰接矩陣中頂點結點
Vertex()的定義可以參考這篇博客，這里就不在貼出相應的代碼了，
2. 問題來源
??假如我從城市
A
A
A出發坐火車去其他城市旅游，那么如何規劃路線使所花費的車票錢最少呢？若將上述圖中的城市看成有向網中的頂點，并將兩城市之間所需要的車票錢看做對應弧的權值，那么這一問題的本質就是求兩個頂點之間權值最小的路徑，簡稱最短路徑
(
S
h
o
r
t
e
s
t
(Shortest
(Shortest
P
a
t
h
)
Path)
Path)，
3. Dijkstra演算法
??
D
i
j
k
s
t
r
a
Dijkstra
Dijkstra演算法，中文名叫迪杰斯特拉演算法，它常用于求解源點到其余頂點的最短路徑，
??假設
G
=
{
V
,
{
A
}
}
G=\{V, \{A\}\}
G={V,{A}}是含有
n
n
n個頂點的有向網，以該圖中的頂點
v
v
v為源點，使用
D
i
j
k
s
t
r
a
Dijkstra
Dijkstra演算法求頂點
v
v
v到圖中其余各頂點的最短路徑的基本思路如下：
??(1) 使用集合
S
S
S記錄已求得最短路徑的終點，初始時
S
=
{
v
}
S=\{v\}
S={v}；
??(2) 選擇一條長度最短的路徑，該路徑的終點
w
∈
V
?
S
w\in V-S
w∈V?S，將
w
w
w并入
S
S
S，并將該最短路徑的長度記為
D
w
D_w
Dw?；
??(3) 對于
V
?
S
V-S
V?S中任一頂點
s
s
s，將源點到頂點
s
s
s的最短路徑長度記為
D
s
D_s
Ds?，并將頂點
w
w
w到頂點
s
s
s的弧的權值記為
D
w
s
D_{ws}
Dws?，若
D
w
+
D
w
s
<
D
s
D_w+D_{ws}<D_s
Dw?+Dws?<Ds?，則將源點到頂點
s
s
s的最短路徑的長度修改為
D
w
+
D
w
s
D_w+D_{ws}
Dw?+Dws?；
??(4) 重復執行上述操作，直到
S
=
V
S=V
S=V，
??
D
i
j
k
s
t
r
a
Dijkstra
Dijkstra演算法有些
P
r
i
m
Prim
Prim演算法的影子，這里使用一個輔助串列Dist，用來存盤源點到每一個終點的最短路徑長度，串列Path來存盤每一條最短路徑中倒數第二個頂點的下標(弧尾下標)，除此之外還需要一個串列flag來記錄頂點是否已求得最短路徑，下面結合著
D
i
j
k
s
t
r
a
Dijkstra
Dijkstra演算法來分析一下上面的那個有向網：
??(1) 這里要做的就是更新串列Dist和串列Path，假如以頂點
A
A
A為起始點，先將它加入
S
S
S中，然后尋找以頂點
A
A
A為弧尾的最短路徑，這里找到了頂點
B
B
B，然后繼續找下一個頂點，這個時候就要做一個判斷了，即
D
w
+
D
w
s
<
D
s
D_w+D_{ws}<D_s
Dw?+Dws?<Ds?是否成立，這里的頂點
s
s
s有兩種選擇，要么是頂點
C
C
C，要么是頂點
D
D
D，因為這兩個頂點都是以頂點
w
w
w(即頂點
B
B
B)為弧尾，按照順序，這個時候先選擇了頂點
C
C
C，經判斷：
D
A
B
+
D
B
C
<
D
A
C
D_{AB}+D_{BC}<D_{AC}
DAB?+DBC?<DAC?(即
4
+
3
=
7
<
8
4+3=7<8
4+3=7<8)成立，然后更新源點到頂點
s
s
s(即頂點
C
C
C)的距離為7，這個時候頂點
s
s
s又選擇了頂點
D
D
D，經判斷：
D
A
B
+
D
B
D
<
D
A
D
D_{AB}+D_{BD}<D_{AD}
DAB?+DBD?<DAD?(即
4
+
8
=
12
<
∞
4+8=12<\infty
4+8=12<∞)成立，然后更新源點到頂點
s
s
s(即頂點
D
D
D)的距離為12，
??(2) 然后尋找以頂點
C
C
C為弧尾的最短路徑，這里找到了頂點
E
E
E，然后做一個路徑長度判斷，經判斷：
D
A
C
+
D
C
E
<
D
A
E
D_{AC}+D_{CE}<D_{AE}
DAC?+DCE?<DAE?(即
7
+
1
=
8
<
∞
7+1=8<\infty
7+1=8<∞)成立，然后更新源點到頂點
s
s
s(即頂點
E
E
E)的距離為8，然后又找到了頂點
F
F
F，然后做一個路徑長度判斷，經判斷：
D
A
C
+
D
C
F
<
D
A
F
D_{AC}+D_{CF}<D_{AF}
DAC?+DCF?<DAF?(即
7
+
6
=
13
<
∞
7+6=13<\infty
7+6=13<∞)成立，然后更新源點到頂點
s
s
s(即頂點
F
F
F)的距離為13，
??(3) 直至計算出所有源點到其余頂點的距離，
??
D
i
j
k
s
t
r
a
Dijkstra
Dijkstra演算法代碼實作如下：
def Dijkstra(self, Vertex):
"""
Dijkstra演算法, 計算源點Vertex到其余各頂點的最短距離
:param Vertex:
:return:
"""
# 源點到每一個終點的最短路徑長度
Dist = []
# 每一條最短路徑中倒數第二個頂點的下標(弧尾下標)
Path = []
# 記錄頂點是否已求得最短路徑
flag = [False] * self.vexnum
index = 0
while index < self.vexnum:
Dist.append(self.arcs[Vertex][index])
if self.arcs[Vertex][index] < float('inf'):
# 存放弧尾下標
Path.append(Vertex)
else:
Path.append(-1)
index += 1
# 以頂點Vertex為源點
Dist[Vertex] = 0
Path[Vertex] = 0
flag[Vertex] = True
index = 1
while index < self.vexnum:
minDist = float('inf')
# 尋找源點到下一個頂點wVertex的最短路徑
for i in range(self.vexnum):
if not flag[i] and Dist[i] < minDist:
wVertex = i
minDist = Dist[i]
flag[wVertex] = True
sVertex = 0
minDist = float('inf')
# 更新源點到終點sVertex的最短路徑
while sVertex < self.vexnum:
if not flag[sVertex]:
if self.arcs[wVertex][sVertex] < minDist and \
Dist[wVertex] + self.arcs[wVertex][sVertex] < Dist[sVertex]:
# 距離更新
Dist[sVertex] = Dist[wVertex] + self.arcs[wVertex][sVertex]
Path[sVertex] = wVertex
sVertex += 1
index += 1
# 輸出資訊
self.ShortestPathDijkstra(Vertex, Dist, Path)
def ShortestPathDijkstra(self, Vertex, Dist, Path):
"""
輸出從頂點Vertex到其余頂點的最短路徑
:param Vertex:
:param Dist:
:param Path:
:return:
"""
tPath = []
index = 0
while index < self.vexnum:
# index是路徑終點
if index != Vertex:
print('頂點' + self.vertexs[Vertex].data + '到達頂點' + self.vertexs[index].data + '的路徑及長度為:')
# 從源點Vertex到終點index中間有可能經過了多個頂點
tPath.append(index)
former = Path[index]
while former != Vertex:
tPath.append(former)
former = Path[former]
tPath.append(Vertex)
while len(tPath) > 0:
print(self.vertexs[tPath.pop()].data, end='')
print('\t\t%d' % Dist[index])
index += 1
4. Floyd演算法
??
F
l
o
y
d
Floyd
Floyd演算法，中文名叫弗洛伊德演算法，它常用于求解求解每一對頂點之間的最短路徑，
??假設
G
=
{
V
,
{
A
}
}
G=\{V, \{A\}\}
G={V,{A}}是含有
n
n
n個頂點的有向網，使用
F
l
o
y
d
Floyd
Floyd演算法求圖中每一對頂點間的最短路徑的基本思路如下：
??(1) 對于圖
G
G
G中任意兩個頂點
v
v
v和
w
w
w，將頂點
v
v
v和頂點
w
w
w的最短路徑的長度記為
D
v
w
D_{vw}
Dvw?，并依次判斷其余各頂點是否為這兩個頂點間最短路徑上的頂點，對于除了頂點
v
v
v和頂點頂點
w
w
w的任意頂點
u
u
u，將頂點
v
v
v和頂點
u
u
u的最短路徑的長度記為
D
v
u
D_{vu}
Dvu?，并頂點
u
u
u和頂點
w
w
w的最短路徑的長度記為
D
u
w
D_{uw}
Duw?，若
D
v
u
+
D
u
w
<
D
v
w
D_{vu}+D_{uw}<D_{vw}
Dvu?+Duw?<Dvw?，則將
D
v
w
D_{vw}
Dvw?的值修改為
D
v
u
+
D
u
w
D_{vu}+D_{uw}
Dvu?+Duw?，即頂點
v
v
v和頂點
w
w
w的最短路徑經過頂點
u
u
u；
??(2) 重復上述程序，直至圖中每一頂點間的最短路徑都被求出，
??當然了，也可以對每個頂點使用
D
i
j
k
s
t
r
a
Dijkstra
Dijkstra演算法來求得每對頂點的最短路徑，對于
F
l
o
y
d
Floyd
Floyd演算法，這里使用一個輔助二維陣列Dist，用來存盤源點到每一對頂點間的最短路徑長度，二維陣列Path來存盤每一條最短路徑中倒數第二個頂點的下標(弧尾下標)，下面結合著
F
l
o
y
d
Floyd
Floyd演算法來分析一下最上面的那個有向網（由于頂點對較多，這里選擇
A
?
I
A-I
A?I的最短路徑進行說明）：
??
F
l
o
y
d
Floyd
Floyd演算法代碼實作如下：
def Floyd(self):
"""
Floyd演算法, 計算每一對頂點間的最短距離
:return:
"""
Dist = [[0 for _ in range(self.vexnum)] for _ in range(self.vexnum)]
Path = [[0 for _ in range(self.vexnum)] for _ in range(self.vexnum)]
for row in range(self.vexnum):
for column in range(self.vexnum):
Dist[row][column] = self.arcs[row][column]
if self.arcs[row][column] < float('inf') and row != column:
Path[row][column] = row
else:
Path[row][column] = -1
# 判斷圖中任意兩個頂點的最短路徑是否經過了結點uVertex
for uVertex in range(self.vexnum):
for vVertex in range(self.vexnum):
for wVertex in range(self.vexnum):
if vVertex != wVertex and \
Dist[vVertex][uVertex] + Dist[uVertex][wVertex] < Dist[vVertex][wVertex]:
Dist[vVertex][wVertex] = Dist[vVertex][uVertex] + Dist[uVertex][wVertex]
Path[vVertex][wVertex] = Path[uVertex][wVertex]
# 輸出每一組頂點間的最短路徑
self.ShortestPathFloyd(Dist, Path)
def ShortestPathFloyd(self, Dist, Path):
"""
輸出每一組頂點間的最短路徑
:param Dist:
:param Path:
:return:
"""
tPath = []
for start in range(self.vexnum):
for end in range(self.vexnum):
if start != end and Dist[start][end] < float('inf'):
print('從頂點' + self.vertexs[start].data + '到頂點' + self.vertexs[end].data +
'的路徑及長度為:')
tVertex = Path[start][end]
tPath.append(end)
while tVertex != -1 and tVertex != start:
tPath.append(tVertex)
tVertex = Path[start][tVertex]
tPath.append(start)
while len(tPath) > 0:
print(self.vertexs[tPath.pop()].data, end='')
print('\t\t%d' % Dist[start][end])
5. 代碼測驗
??測驗代碼如下：
if __name__ == '__main__':
graph = Graph(kind='Dinetwork')
graph.CreateGraph(vertex_list=['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'],
edge_list=[('A', 'B', 4), ('A', 'C', 8), ('B', 'C', 3), ('B', 'D', 8),
('C', 'E', 1), ('C', 'F', 6), ('D', 'G', 7), ('D', 'H', 4),
('E', 'D', 2), ('E', 'F', 6), ('F', 'H', 2), ('G', 'I', 9),
('H', 'G', 14), ('H', 'I', 10)])
print('{:*^30}'.format('Dijkstra演算法'))
# 起始位置的index為0
graph.Dijkstra(0)
print('{:*^30}'.format('Floyd演算法'))
graph.Floyd()
??測驗結果如下：
??這里只看了一條，就是從頂點
A
A
A到頂點
I
I
I的路徑，可以看到
D
i
j
k
s
t
r
a
Dijkstra
Dijkstra演算法和
F
l
o
y
d
Floyd
Floyd演算法求得的最短路徑都是24，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/286960.html
標籤：python
上一篇：C語言超全學習路線（少走彎路）