Pythonデータ構造の図最短パス
Pythonデータ構造の最短パス
単一ソースポイント最短パスのDijkstraアルゴリズム
アルゴリズムの手順: Vを2つのグループ(1)S:最短経路の頂点を求める集合(2)T=V−S:最短経路の頂点集合はまだ決定されていない. は、Tの頂点を最短経路でインクリメントする順序でSに加える.
保証:
(1)ソース点v 0 v_から0 v 0からSまでの各頂点の最短パス長はv 0 v_より大きくない0 v 0からTまでの任意の頂点の最短パス長.
(2)頂点ごとに1つの距離値を指定します.
S中頂点:v 0 v_から0 v 0この頂点の最短パス長は、
T中頂点:v 0 v_から0 v 0この頂点には、Sの頂点のみを中間頂点とする最短パス長が含まれる.
コード:
(1)頂点クラスへのアクセス
(2)隣接図の作成
マルチソース点最短のFloydアルゴリズム
ターゲット:図の各頂点間の最短パスを計算します.
アルゴリズムステップ:初期にn次方程式を設定し、対角線要素を0(すなわち、自身から自身への経路が0)にし、アークが存在する場合、対応する要素は重みである.そうでなければ無限です.アルゴリズムを行うときは、元のパスに中間ノードを徐々に増やしてみて、中間頂点を加えるとパスが短くなると修正します.そうでなければ、元の値を維持します.すべての頂点のプローブが完了し、アルゴリズムが終了します.
コード:
1)初期化マトリクス1
2)Floydコアアルゴリズム(新しいノードの追加が元のパスを短くしたかどうかを尋ねる)
リファレンス
データ構造とアルゴリズム–フロイドアルゴリズムPythonフロイドアルゴリズムを実現フロイドアルゴリズムを実現一歩一歩フロイドアルゴリズムを実現
データ構造とアルゴリズム–ディジェストラアルゴリズムPythonディジェストラアルゴリズムを実現する一歩一歩Pythonでディジェストラアルゴリズムを実現する
データ構造とアルゴリズムの基礎–第11週08–6.6図の応用8–6.6.2.2最短経路3–Floydアルゴリズム
データ構造とアルゴリズムの基礎–第11週07–6.6図の応用7–6.6.2.2最短経路2–Dijkstraアルゴリズム
単一ソースポイント最短パスのDijkstraアルゴリズム
アルゴリズムの手順:
保証:
(1)ソース点v 0 v_から0 v 0からSまでの各頂点の最短パス長はv 0 v_より大きくない0 v 0からTまでの任意の頂点の最短パス長.
(2)頂点ごとに1つの距離値を指定します.
S中頂点:v 0 v_から0 v 0この頂点の最短パス長は、
T中頂点:v 0 v_から0 v 0この頂点には、Sの頂点のみを中間頂点とする最短パス長が含まれる.
コード:
(1)頂点クラスへのアクセス
class VisitedVertex:
""" """
def __init__(self, length: int, index: int):
"""
:param length:
:param index:
"""
self.index = index
self.ver = None
self.already_array = [0] * length #
self.pre_visited = [0] * length #
self.dis = [float("inf")] * length # ，
# 0
self.dis[index] = 0
self.already_array[index] = 1
def is_visited(self, index: int):
""" """
return self.already_array[index] == 1
def update_dis(self, index: int, length: int):
""" """
self.dis[index] = length
def updata_pre(self, pre: int, index: int):
""" """
self.pre_visited[pre] = index
def get_dis(self, index: int):
""" """
return self.dis[index]
def update_arr(self):
min_val = float("inf")
index = 0
for i in range(len(self.already_array)):
if self.already_array[i] == 0 and self.dis[i] < min_val:
min_val = self.dis[i]
index = i
#
self.already_array[index] = 1
return index
def show_result(self):
print(" ：")
for item in self.already_array:
print(item, end=" ")
print()
for item in self.pre_visited:
print(item, end=" ")
print()
for item in self.dis:
print(item, end=" ")
print()
self.ver = Graph(vertex, matrix)
count: int = 0
for item in self.dis:
if item != float("inf"):
print("{}->{}:distance:{}".format(self.ver.vertex[self.index], self.ver.vertex[count], self.dis[count]))
count += 1
(2)隣接図の作成
class Graph:
""" """
def __init__(self, vertex: [], matrix: []):
self.vertex = vertex #
self.matrix = matrix #
self.vv = None
def show_djs(self):
self.vv.show_result()
def show_graph(self):
""" """
for col in self.matrix:
print(col)
def djs(self, index: int):
""" """
self.vv = VisitedVertex(len(self.vertex), index)
#
self.updata(index)
# n-1
for j in range(1, len(self.vertex)):
#
index = self.vv.update_arr()
#
self.updata(index)
def updata(self, index):
""" S """
length: int = 0
for j in range(len(self.matrix[index])):
#
length = self.vv.get_dis(index) + self.matrix[index][j]
#
if not self.vv.is_visited(j) and length < self.vv.get_dis(j):
self.vv.updata_pre(j, index)
self.vv.update_dis(j, length)
if __name__ == "__main__":
vertex: [] = ["A", "B", "C", "D", "E", "F", "G"]
matrix: [] = [[0 for col in range(len(vertex))] for row in range(len(vertex))]
#
F: float = float('inf')
matrix[0] = [0, 5, 7, F, F, F, 2]
matrix[1] = [5, 0, F, 9, F, F, 3]
matrix[2] = [7, F, 0, F, 8, F, F]
matrix[3] = [F, 9, F, 0, F, 4, F]
matrix[4] = [F, F, 8, F, 0, 5, 4]
matrix[5] = [F, F, F, 4, 5, 0, 6]
matrix[6] = [2, 3, F, F, 4, 6, 0]
g = Graph(vertex, matrix)
g.show_graph()
g.djs(6)
g.show_djs()
マルチソース点最短のFloydアルゴリズム
ターゲット:図の各頂点間の最短パスを計算します.
アルゴリズムステップ:初期にn次方程式を設定し、対角線要素を0(すなわち、自身から自身への経路が0)にし、アーク
コード:
1)初期化マトリクス1
# matrix
matrix[0] = [0, 5, 7, F, F, F, 2]
matrix[1] = [5, 0, F, 9, F, F, 3]
matrix[2] = [7, F, 0, F, 8, F, F]
matrix[3] = [F, 9, F, 0, F, 4, F]
matrix[4] = [F, F, 8, F, 0, 5, 4]
matrix[5] = [F, F, F, 4, 5, 0, 6]
matrix[6] = [2, 3, F, F, 4, 6, 0]
2)Floydコアアルゴリズム(新しいノードの追加が元のパスを短くしたかどうかを尋ねる)
def floyd(self):
"""Floyd :"""
length: int = 0
for k in range(len(self.dis)): # ( )
for i in range(len(self.dis)):
for j in range(len(self.dis)):
length = self.dis[i][k] + self.dis[k][j]
if length < self.dis[i][j]:
self.dis[i][j] = length
self.pre[i][j] = self.pre[k][j]
リファレンス
データ構造とアルゴリズム–フロイドアルゴリズムPythonフロイドアルゴリズムを実現フロイドアルゴリズムを実現一歩一歩フロイドアルゴリズムを実現
データ構造とアルゴリズム–ディジェストラアルゴリズムPythonディジェストラアルゴリズムを実現する一歩一歩Pythonでディジェストラアルゴリズムを実現する
データ構造とアルゴリズムの基礎–第11週08–6.6図の応用8–6.6.2.2最短経路3–Floydアルゴリズム
データ構造とアルゴリズムの基礎–第11週07–6.6図の応用7–6.6.2.2最短経路2–Dijkstraアルゴリズム