class Graph(object):
 """
 以鄰接矩陣為存儲結(jié)構(gòu)創(chuàng)建有向網(wǎng)
 """
 def __init__(self, kind):
  # 圖的類型: 無向圖, 有向圖, 無向網(wǎng), 有向網(wǎng)
  # kind: Undigraph, Digraph, Undinetwork, Dinetwork,
  self.kind = kind
  # 頂點(diǎn)表
  self.vertexs = []
  # 邊表, 即鄰接矩陣, 是個(gè)二維的
  self.arcs = []
  # 當(dāng)前頂點(diǎn)數(shù)
  self.vexnum = 0
  # 當(dāng)前邊(弧)數(shù)
  self.arcnum = 0
 def CreateGraph(self, vertex_list, edge_list):
  """
  創(chuàng)建圖
  :param vertex_list: 頂點(diǎn)列表
  :param edge_list: 邊列表
  :return:
  """
  self.vexnum = len(vertex_list)
  self.arcnum = len(edge_list)
  for vertex in vertex_list:
vertex = Vertex(vertex)
# 頂點(diǎn)列表
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):
  """
  定位頂點(diǎn)在鄰接表中的位置
  :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):
  """
  創(chuàng)建鄰接矩陣
  :param ivertex:
  :param jvertex:
  :param weight:
  :return:
  """
  if self.kind == 'Dinetwork':
self.arcs[ivertex][jvertex] = weight

 def Dijkstra(self, Vertex):
  """
  Dijkstra算法, 計(jì)算源點(diǎn)Vertex到其余各頂點(diǎn)的最短距離
  :param Vertex:
  :return:
  """
  # 源點(diǎn)到每一個(gè)終點(diǎn)的最短路徑長度
  Dist = []
  # 每一條最短路徑中倒數(shù)第二個(gè)頂點(diǎn)的下標(biāo)(弧尾下標(biāo))
  Path = []
  # 記錄頂點(diǎn)是否已求得最短路徑
  flag = [False] * self.vexnum
  index = 0
  while index < self.vexnum:
Dist.append(self.arcs[Vertex][index])
if self.arcs[Vertex][index] < float('inf'):
 # 存放弧尾下標(biāo)
 Path.append(Vertex)
else:
 Path.append(-1)
index += 1
  # 以頂點(diǎn)Vertex為源點(diǎn)
  Dist[Vertex] = 0
  Path[Vertex] = 0
  flag[Vertex] = True
  index = 1
  while index < self.vexnum:
minDist = float('inf')
# 尋找源點(diǎn)到下一個(gè)頂點(diǎn)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')
# 更新源點(diǎn)到終點(diǎn)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):
  """
  輸出從頂點(diǎn)Vertex到其余頂點(diǎn)的最短路徑
  :param Vertex:
  :param Dist:
  :param Path:
  :return:
  """
  tPath = []
  index = 0
  while index < self.vexnum:
# index是路徑終點(diǎn)
if index != Vertex:
 print('頂點(diǎn)' + self.vertexs[Vertex].data + '到達(dá)頂點(diǎn)' + self.vertexs[index].data + '的路徑及長度為:')
 # 從源點(diǎn)Vertex到終點(diǎn)index中間有可能經(jīng)過了多個(gè)頂點(diǎn)
 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

 def Floyd(self):
  """
  Floyd算法, 計(jì)算每一對頂點(diǎn)間的最短距離
  :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
  
  # 判斷圖中任意兩個(gè)頂點(diǎn)的最短路徑是否經(jīng)過了結(jié)點(diǎn)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]
  # 輸出每一組頂點(diǎn)間的最短路徑
  self.ShortestPathFloyd(Dist, Path)
 def ShortestPathFloyd(self, Dist, Path):
  """
  輸出每一組頂點(diǎn)間的最短路徑
  :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('從頂點(diǎn)' + self.vertexs[start].data + '到頂點(diǎn)' + 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])

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()