アルゴリズムベース-最短パスアルゴリズム

🌈 マルチアウトレットアルゴリズム(最短パス)

🔥 最短パスアルゴリズムとは?

🔥 優先順位キューを利用したマルチアウトプットアルゴリズムロジック

🔥 優先キューによる複数のアルゴリズムの実装

最短パスアルゴリズムとは?

1)最短パスアルゴリズムタイプ

2.優先順位キューを利用したマルチアウトプットアルゴリズムロジック

、すなわち、より多くのノードを通っても虫歯の和の最小経路は最短経路

1）ステップ1：初期化

優先キューには、まず最初の頂点(距離0)

2）ステップ2：優先順位キューから抽出した（A，0）［ノード，1番目のノードからの距離］から隣接ノードからの距離を算出する

優先キューは最小hip構造であるため、追加順序にかかわらず、最前面に最小値

3）ステップ3：優先順位キュー（C，1）［ノード、1番目のノードとの距離］から隣接ノードとの距離を計算する

から保存A-Dまでの距離は2、A->C->D経路は3であるため、Dの距離は

4）ステップ4：優先順位キュー（D，2）［ノード，1番目のノードからの距離］から隣接ノードの距離を計算する

A->Dまでの距離、D->Fは5、Fを加えると、7

5）ステップ5：優先順位キュー（E，5）［ノード、最初のノードからの距離］に基づいて、この隣接ノードからの距離を計算する

(F,7)が(F,6)

6)ステップ6:優先順位キューから(B,6)(F,6)を順次抽出し、各ノードから隣接ノードとの距離を算出する

FノードにはAノードへの経路があるが、A-Aは0であるためより小さい、

7)ステップ7:優先順位キューから順に抽出(F,7)(B,8)し、各ノードから隣接ノードとの距離を算出する

8）ステップ8：A-Bまでのルート距離が8であるが、アレイ内のA-Bルートはすでに6であるため、距離を計算する必要がない

3.マルチアウトレットアルゴリズムの実現

1)heaqライブラリの利用

# heapq 라이브러리 활용하여 우선순위 큐 사용
import heapq
queue = []
heapq.heappush(queue, [2, 'A'])
heapq.heappush(queue, [5, 'B'])
heapq.heappush(queue, [1, 'C'])
heapq.heappush(queue, [7, 'C'])
print(queue) # [[1, 'C'], [5, 'B'], [2, 'A'], [7, 'C']]
for i in range(len(queue)):
    print(heapq.heappop(queue), end=' ') # [1, 'C'] [2, 'A'] [5, 'B'] [7, 'C'] 

2）図形Python表現

# 구현
mygraph = {
    'A' : {'B':8, 'C':1, 'D':2},
    'B' : {},
    'C' : {'B':5, 'D':2},
    'D' : {'E':3, 'F':5},
    'E' : {'F':1},
    'F' : {'A':5}
}

3）複数曲線アルゴリズムの実現

# 최단 경로 알고리즘
# graph 구현
mygraph = {
    'A': {'B': 8, 'C': 1, 'D': 2},
    'B': {},
    'C': {'B': 5, 'D': 2},
    'D': {'E': 3, 'F': 5},
    'E': {'F': 1},
    'F': {'A': 5}
}
# heapq 라이브러리 활용하여 우선순위 큐 사용
# graph 구현
graph = {
    'A': {'B':8, 'C':1, 'D':2},
    'B': {},
    'C': {'B':5, 'D':2},
    'D': {'E':3, 'F':5},
    'E': {'F':1},
    'F': {'A':5},
}
import heapq
def dijkstra(graph, start):
    distances = {node : float('inf') for node in graph}
    distances[start] = 0 # {'A': 0, 'B': inf, 'C': inf, 'D': inf, 'E': inf, 'F': inf}
    queue = []
    heapq.heappush(queue, [distances[start], start]) # [[0, 'A']]
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        # 이미 distnaces에 저장된 거리가 heap에서 꺼낸 누적된 거리보다 작다면 skip
        if distances[current_node] < current_distance:
            continue
        for adjacent, weight in graph[current_node].items():
            distance = current_distance + weight # 거리 = 현재까지의 거리 + 현재부터 해당 노드까지의 거리
            # 거리가 이미 distances에 저장된 거리보다 작다면 업데이트 후 queue에 추가
            if distance < distances[adjacent]:
                distances[adjacent] = distance
                heapq.heappush(queue, [distance, adjacent])
    return distances
print(dijkstra(graph, 'A'))
# {'A': 0, 'B': 6, 'C': 1, 'D': 2, 'E': 5, 'F': 6}