Condition for loop in Floyd–Warshall algorithm

Question

I'm learning a basic shortest-route algorithm specifically Floyd–Warshall algorithm.

I understood how efficient it is when finding 'All to All' distance.

But while reading a code from the book I'm studying with, I find it something strange

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()

This is the code.

The lines I'm curious about is this.

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])

is it okay to ignore elements that are a==b & a==i & b==I

This is what I think the code should be

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])

Can you tell me the better version and why?

Answer 1

You do not need to handle the cases a==i, b==i, a==b because in this cases nothing happens.

case a==i :

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

becomes:

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

similar for the cases b==i and a==b

---

SPEED:

The if-statement may make sense in terms of speed (to be sure profile/benchmark both versions (with representative input data) But even if handling these cases makes sense you should skip as early as possible.

for i in range(1,node_n+1) :
    for a in range(1,node_n+1) :
        if a != i:   // you can skip the b-loop in this case
            for b in  range(1,node_n+1) :
                if b != i and a != b :   // I'm not sure if this improves or even decreases the speed
                    graph[a][b] = min(graph[a][b], graph[a][i]+graph[i][b])