マルチ出口アルゴリズム-最短パス

単一始点最短パスアルゴリズム
頂点には、開始点に近い順にアクセスします.
優先順位キューを使用して、キュー内の頂点番号を、これまでに見つかった頂点の最短距離にペアリングし、最短距離を基準に頂点を並べます->まだアクセスされていない頂点で、開始点に最も近い点を探します.
頂点にアクセスするたびに、隣接するすべての頂点がチェックされます.
負の周期がなく、負の幹線がある場合に使用することは推奨されませんが、時間の複雑さは指数関数的に増加します.
時間の複雑さ
優先順位キューにより、すべての幹線が1回チェックされます->O(간선수)優先順位キューの最大の最悪の場合、すべての幹線をチェックするたびに、すべての頂点がキューに追加されます->追加された最大頂点数->O(간선수)、各要素が追加され、O(log간선수)->O(幹線選手log幹線数)が削除されます.
最終的にはO(幹線数log幹線数)またはO(幹線数log頂点数)
優先キューを無効にします.

ポイントの数が少ないか、幹線の数が多い場合は、優先順位キューを無効にすると、より高速になる可能性があります.

アクセスする頂点

は、重複文を使用するたびにアクセスしない頂点の始点距離の最小値を検索するのではなく、キューに入れられます.

各サイトへのアクセスは、アレイに

を格納する必要があります.
コード#コード#distanceには、開始頂点からの最短経路が格納され、visitedは、最短経路が特定されたかどうかを確認するために設けられた最初の円アレイである.
アルゴリズムの各ステップは、アクセスされていない頂点の中で最も距離の小さい頂点をアクセスに追加します.新しい頂点uがアクセスに追加されると、他の未アクセス頂点の距離値が変更される.( u를 거쳐서 정점까지 가는 거리와 기존의 거리를 비교 )

int_max = 10001
max_dot = 7 # 정점의 수
weight = [[0,7,int_max,int_max,3,10,int_max], [7,0,4,10,2,6,int_max],[int_max,4,0,2,int_max,int_max,int_max],[int_max,10,2,0,11,9,4],[3,2,int_max,11,0,int_max,5],[10,6,int_max,9,int_max,0,int_max],[int_max,int_max,int_max,4,5,int_max,0]]

distance = [int_max for _ in range(max_dot)] # 시작 정점으로부터 최단 경로 거리
visited = [False for _ in range(max_dot)] # 방문한 정점 표시

# 아직 방문하지 않은(집합 S에 있지 않은) 정점들 중 가중치가 가장 적은 정점 반환
def newDot():
    m = int_max
    k = -1
    for i in range(max_dot): 
        if not visited[i]: 
            if m > distance[i]: 
                m = distance[i]
                k = i
    return k

def dijkstra():
    global visited
    global distance # 시작 정점으로부터의 최단 경로

    for i in range(max_dot):
        distance[i] = weight[0][i] # 기본 가중치로 초기화

    while not all(visited): # visited 가 모두 True 가 아닐때까지 == 모든 정점을 방문하기 전까지
        d = newDot() # 가중치가 가장 적은 정점을 가져와서
        visited[d] = True # 방문한 후 
        for j in range(max_dot): # 다른 정점들의 가중치를 갱신
            distance[j] = min(distance[j], distance[d] + weight[d][j])

dijkstra()
print(distance)