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

📌 最短パスアルゴリズム
SWEAの1249.補給線問題を解く際に,最小コストで目標を達成する最短経路アルゴリズムを探した.従って,整理されたマルチアウトレットアルゴリズムを用いて最短経路を実現する.
まず最短パスを求める方法は、最初の頂点を基準に接続された頂点を追加し、最短距離を更新することがコアです.

の最初の頂点から、各ノード間の距離を格納する配列が生成される.

の最初の頂点の隣接ノード間の距離から計算を開始し、最短距離を配列に更新します.

最初の頂点から各ノードまでの距離を格納し、各ノードまでの最小距離を比較して更新する配列を作成します.距離と優先キューを格納する必要があります.
📌 heapqライブラリの利用
注意、heapqはsotのように要素全体をソートするのではなく、最小値を持つ要素を一番前に並べます!

import heapq

queue = []

heapq.heappush(queue, [2, 'A'])
heapq.heappush(queue, [5, 'B'])
heapq.heappush(queue, [1, 'C'])
heapq.heappush(queue, [7, 'D'])
print(queue)
for index in range(len(queue)):
    print(heapq.heappop(queue))
    
    
> [[1, 'C'], [5, 'B'], [2, 'A'], [7, 'D']]
  [1, 'C']
  [2, 'A']
  [5, 'B']
  [7, 'D']

📌 マルチアウトレットアルゴリズム
優先キューが使用されているため、これまでに発見された最短距離のノードを先に計算し、計算長さの長いルーティングをスキップすることができます.

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}
}

import heapq

def dijkstra(graph, start):
    
    # 초기화
    
    # 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장. 초기에는 첫 정점의 거리는 0, 나머지는 무한대로 저장함
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = [] # 우선순위 큐
    heapq.heappush(queue, [distances[start], start]) # 우선순위 큐에 첫 정점 저장
    
    # 우선순위 큐가 빌 때까지 노드를 꺼낸다.
    while queue:
        current_distance, current_node = heapq.heappop(queue) # 우선순위 큐에서 꺼낸 첫 정점의 거리와 번호
        
        if distances[current_node] < current_distance:
            continue
        
        # 배열에서 꺼낸 첫 정점거리 + 배열에서 꺼낸 첫 정접부터 연결된 노드까지 거리를 더해서 distance 라는 변수에 저장
        for adjacent, weight in graph[current_node].items():
            distance = current_distance + weight
            
            # 첫 정점에서 인접한 각 노드로 가는 거리와 현재 배열에 저장되어 있는 첫 정점에서 각 정점까지 거리를 비교
            if distance < distances[adjacent]:
                # 현재 배열에 저장되어 있는 첫 정점에서 인접한 노드로 가는 거리가 더 짧으면 배열을 업데이트
                distances[adjacent] = distance
                # 우선순위 큐에도 추가한다.
                heapq.heappush(queue, [distance, adjacent])
                
    return distances
    
dijkstra(mygraph, 'A')


> {'A': 0, 'B': 6, 'C': 1, 'D': 2, 'E': 5, 'F': 6}

📌 Daextraで解いた<1249.補給路>

import heapq
T = int(input())
for tc in range(1, T+1):
    N = int(input())
    roads = [list(map(int, input())) for _ in range(N)]
    times = [[float('inf')]*N for _ in range(N)]
    times[0][0] = 0
    dir = [(-1,0), (1,0), (0,-1), (0,1)] # 상하좌우
    queue = []
    heapq.heappush(queue, (0, 0, times[0][0])) # x좌표, y좌표, 복구에 걸리는 시간

    while queue:
        x, y, time = heapq.heappop(queue)
        if times[x][y] < time:
            continue

        for d in dir:
            nx, ny = x + d[0], y + d[1]
            setting = time
            if 0 <= nx < N and 0 <= ny < N:
                setting += roads[nx][ny]

                if setting < times[nx][ny]:
                    times[nx][ny] = setting
                    heapq.heappush(queue, (nx, ny, setting))

    print(f'#{tc} {times[N-1][N-1]}')