[最短パス]floywalshアルゴリズムのほかに2つの問題がある

ソース-これがPythonのコードテストです
りゅうすいアルゴリズム
1.多項式アルゴリズムとの比較
マルチアウトプットアルゴリズム-ある点から別の点への最短経路を求めるアルゴリズム.
flowersalアルゴリズム-すべての点から他のすべての点へのすべての最短パスが必要な場合

マルチアウトレットアルゴリズム
各ステップは、最短距離テーブルで最も高い値を持つノードを選択します.
次に、ノードを通過するパスを決定し、最短距離テーブルを更新するように操作します.

りゅうすいアルゴリズム
flowersalアルゴリズムも、各フェーズの「通過ノード」に基づいてアルゴリズムを実行します.

しかし、異なる点は、アクセスされていないノードのたびに、最短距離のノードを見つける必要はありません.
2.floydwalshアルゴリズムの特徴

[最短距離](Short Distance)情報を2 Dリストに格納する機能があります.
-すべてのノードから他のすべてのノードへの最短距離情報を含めるためです.
−2次元リストの処理が必要であるため、NステップではO(N^2)の時間が必要である.(全部でO(N^3)の時間が必要です.)

ダイナミックプログラミングの特徴があります.
-ノードの数がnの場合、n回のステップで「点火式に一致する」2 Dリストが更新されるからです.
具体的な点火式-Dab=min(Dab、Dak+Dkb)
(a->bへの移動とa->k->bへの移動のコストを比較)

3.FloyWarshアルゴリズムの実装
本の中の過程をそのままコードに書き,以下に示す.

INF = int(1e9) #무한 값 설정

n = int(input()) #노드의 수
m = int(input()) #간선의 수 

graph = [[INF]*(n+1) for i in range(n+1)] #2차원 리스트를 만들고 모든 값을 INF로 초기화

#자기 자신으로 가는 비용은 0으로 초기화
for i in range(1,n+1):
    for j in range(1,n+1):
        if i==j:
            graph[i][j] = 0

#간선과 비용 입력받기
for i in range(m):
    s,e,dist = map(int,input().split())
    graph[s][e] = dist #단방향 그래프

#플로이드 워셜 실행
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            graph[i][j] = min(graph[i][j],graph[i][k]+graph[k][j])
            

for i in range(1,n+1):
    for j in range(1,n+1):
        if graph[i][j]==INF:
            print("INF", end=" ")
        else:
            print(graph[i][j], end=" ")
    print()

Flowersalアルゴリズムを実行するコードは次のとおりです.

#플로이드 워셜 실행
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            graph[i][j] = min(graph[i][j],graph[i][k]+graph[k][i])

この部分です
この場合、for文の順序に注意してください.

最初のk:通過ノード

中間i:開始ノード

最後のj:到着ノード

エラーの場合
最初のk:開始ノード
中間i:ノードに到達
最後のj:通るノードと言えば
たとえば、図[1][2]の最小コストを取得したい場合.

for j in range(1,n+1):
	graph[1][2] = min(graph[1][2],graph[1][j]+graph[j][2])

修行を積む.
このようにgraph[1][2]の値は、ステップごとに更新されるのではなく、実行されて終了する.
=>通過するノードを基準として、ステップごとに更新する必要があります.
2つの問題.
未来の都市
1.floydwalsh解読方式

INF = int(1e9)
#노드와 간선 입력
n,m = map(int,input().split())

graph =[[INF]*(n+1) for i in range(n+1)] #무한대로 초기화한 그래프 생성

#자기자신은 0으로 맞춤
for i in range(1,n+1):
    for j in range(1,n+1):
        if i==j:
            graph[i][j]=0

#m개의 간선 입력받기 
for i in range(m):
    s,e = map(int,input().split())
    graph[s][e]=1 #양방향 그래프+거리는 무조건 1
    graph[e][s]=1

#마지막 줄에 x,k입력받기
x,k = map(int,input().split())

#플로이드 워셜 알고리즘 수행
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            graph[i][j] = min(graph[i][j],graph[i][k]+graph[k][j])

if graph[1][k]==INF or graph[k][x]==INF:
    print(-1)
else:
    print(graph[1][k]+graph[k][x])

floydwalshアルゴリズムにより,すべての開始ノードからすべての到達ノードまでの距離(1−>k費用)+(k−>x費用)を求めた.
2.マルチアウトレットアルゴリズム

import heapq

INF = int(1e9)
#노드와 간선 입력
n,m = map(int,input().split()) #노드와 간선 입력받기

graph = [[] for i in range(n+1)] #빈 인접리스트 생성
distance = [INF]*(n+1) #1차원의 거리 리스트 생성

#간선 입력 받기
for i in range(m):
    s,e = map(int,input().split())
    graph[s].append([e,1])
    graph[e].append([s,1]) #양방향 그래프 (노드, 거리)

x,k = map(int,input().split()) #x,k입력받기

def dijkstra(start):
    q = []
    distance[start] = 0 #출발노드는 거리 0
    heapq.heappush(q,(0,start))
    
    while q:
        dist,node = heapq.heappop(q)
        if distance[node] < dist: #이미 방문했었던 노드라면 무시
            continue
        for i in graph[node]:
            cost = dist+i[1]
            if distance[i[0]] > cost:
                distance[i[0]] = cost
                heapq.heappush(q,(cost,i[0]))

#1에서 k까지 구하기
dijkstra(1)
answer = distance[k]

#k에서 x까지 구하기
dijkstra(k)
answer+=distance[x]

if answer>=INF:
    print("-1")
else:
    print(answer)

まず多出力アルゴリズムを実現し,2次関数呼び出しにより結果値を得た.
でんしん

import heapq

#무한대 값 설정하기
INF = int(1e9)

#노드, 간선, 출발지
n,m,c = map(int, input().split())

graph=[[] for i in range(n+1)]
distance=[INF]*(n+1)

#간선, 비용 입력받기
for i in range(m):
    x,y,z = map(int,input().split())
    graph[x].append([y,z]) #단방향 그래프
    
def dijkstra(start):
    q=[]
    distance[start] = 0
    heapq.heappush(q,(0,start)) #시작노드 push
    
    while q:
        dist, node = heapq.heappop(q)
    
        if distance[node] <dist: #이미 방문한 노드
            continue
        
        for i in graph[node]:
            cost = distance[node]+i[1] #출발지부터 node+ node부터 i[0]까지의 거리
            
            if cost<distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q,(cost,i[0]))
                
count=0
total = 0
dijkstra(c)

for i in range(1,n+1):
    if distance[i]!=INF:
        count+=1
        total = max(total, distance[i])
        
#count에서 자기 자신은 뺀다. 
print(count-1, total)

開始ノードが与えられたので,マルチ出口アルゴリズムを用いて実現した.
出発ノードは回転可能なノードの個数を求めるので,距離リストの値がINFでなければcount+=1とする.