Dijkstra's algorithm(ディックストラアルゴリズム)

2676 ワード

Algorithm

概要

ディックストラアルゴリズムは,負のエッジを含まない重みマップにおける単一ソース最短パス問題に用いる1つの頂点から残りの各頂点への最短パスアルゴリズムである.BFS(幅優先探索)と同様である.

方法

priorityの準備Queue(優先キュー)、push開始点とその最短距離までの情報(開始点00、その他の頂点∞).優先キューが使用されているため、情報は最短距離でソートされます.

は、優先キューが空のセットになるまで、次の操作を繰り返します.

優先キューの先頭要素(最も短い距離の要素)

を抽出する.

抽出された要素に含まれる距離情報が記録された最短距離よりも大きい場合、その動作は終了し、操作はプリアンブル抽出の動作に戻る.

は、そこから移動可能な頂点をスキャンし、最短距離を更新できる頂点があれば、その距離を更新し、その頂点までの距離、頂点の情報pushを優先キューに移動する.

複雑度はO(ElogV)である.

ぎじふごう

// V:    
// Q:          （  ，      ）  
// d(v):              
// prev(v):             

//    
for (v  alt )
        d(v)

Pythonコード

import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
        if self.goal_point is not None:
            return self.get_path(self.goal_point, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))

#     
n = int(input())
s, t = map(int, input().split())
route_map = [dict() for _ in range(n)]
for i in range(n):
    u, v, a = map(int, input().split())
    u, v = u - 1, v - 1
    route_map[u][v] = a

#                   
dijkstra_result = Dijkstra(route_map, s - 1).execute()

#            
dijkstra_result = Dijkstra(route_map, s - 1, t - 1).execute()

Dijkstra's algorithm(ディックストラアルゴリズム)

概要

方法

ぎじふごう

Pythonコード

関連する問題