Dijkstra 다익스트라, Prim과의 차이점

Dijkstra 다익스트라

출발점으로부터 각 정점까지의 최단거리 및 경로 계산

Prim-MST 알고리즘과 유사. 차이점은 Dijkstra-최단경로는 출발점이 주어진다는 것, D의 원소에 출발점부터의 경로의 길이가 저장된다는 것!

Prim→어느 정점에서 시작해도 같은 그래프를 도출 / D의 원소에 자신과 연결된 간선의 가중치를 저장

Dijkstra→특정 정점으로부터의 최단 경로를 구하기 때문에 시작 정점이 바뀔 때마다 최단 경로 그래프가 다르게 도출 / D의 원소에 출발점부터의 경로의 길이를 저장

for k in range(N):
    m=-1 # m:min_vertex
    min_value=sys.maxsize

    # 가장 가까운 정점찾기
    for j in range(N):
        if not visited[j] and D[j]<min_value:
            min_value=D[j]
            m=j
    visited[m]=True

    # 정점 m에 인접한 w와 (m,w)의 가중치 wt에 대해
    for w,wt in list(g[m]):
        if not visited[w]:
            if D[m] + wt < D[w]:
                D[w]=D[m]+wt #Prim 알고리즘과 다른 부분
                previous[w]=m