Floyd–Warshall 算法中的循环条件

Question

我正在学习基本的最短路线算法，特别是 Floyd–Warshall 算法。

我了解了寻找“All to All”距离时的效率。

但是在阅读我正在学习的书中的代码时，我发现它有些奇怪

INF = int(1e9)

# 노드와 간선의 개수
node_n = int(input())
edge_e = int(input())

# 2차원 리스트(그래프 표현)를 만들고 모든 값을 무제한으로 초기화
graph = [[INF] * (node_n+1) for _ in range(node_n+1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화 
for i in range(node_n+1) :
    graph[i][i] = 0

# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for i in range(edge_e) :
    a, b, c = map(int,input().split())
    if c < graph[a][b] :
        graph[a][b] = c

# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for i in range(1,node_n+1) :
    for a in range(1,node_n+1) :
        for b in  range(1,node_n+1) :
            if a != i and b != i and a != b :
                graph[a][b] = min(graph[a][b], graph[a][i]+graph[i][b])

# 수행된 결과를 출력
for a in range(1,node_n+1) :
    for b in range(1,node_n+1) :
        if graph[a][b] == INF :
            print(0, end=' ')
            continue
        print(graph[a][b], end=' ')
    print()

这是代码。

我好奇的台词是这个。

for i in range(1,node_n+1) :
    for a in range(1,node_n+1) :
        for b in  range(1,node_n+1) :
                graph[a][b] = min(graph[a][b], graph[a][i]+graph[i][b])

是否可以忽略 a==b & a==i & b==I 的元素

这就是我认为代码应该是的

for i in range(1,node_n+1) :
    for a in range(1,node_n+1) :
        for b in  range(1,node_n+1) :
            if a != i and b != i and a != b :
                graph[a][b] = min(graph[a][b], graph[a][i]+graph[i][b])

你能告诉我更好的版本以及为什么吗？

Answer 1

您不需要处理 a==i、b==i、a==b 的情况，因为在这种情况下什么也不会发生。

案例

a==i 

：

graph[a][b] = min(graph[a][b], graph[a][a]+graph[a][b])

变成：

graph[a][a]==0  ->   
graph[a][b] = min(graph[a][b], graph[a][b]) = graph[a][b]  
// is the same as 'DO NOTHING'

情况类似

b==i

和

a==b