[CS] 플로이드 워셜 이해 안되는 점
2023. 8. 23. 13:59ㆍCS
과연 시작되는 순서가 바뀐다고 해도 결과는 같을까?
결과적으로 for문의 순서를 바꿔도 같고 iteration 숫자를 바꿔도 같다.
왜 그런지는 잘 모르겠다.
def floyd():
# k는 경유하는 노드
for i in range(1, NODE_CNT+1):
for j in range(1, NODE_CNT+1):
for k in range(1, NODE_CNT+1):
# k노드를 경유하는 거리값이 더 작으면 갱신
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
if __name__ == "__main__":
NODE_CNT = 4
INF = 2147000000
graph = [[INF] * (NODE_CNT + 1) for _ in range(NODE_CNT + 1)]
for i in range(1, NODE_CNT + 1):
graph[i][i] = 0
graph[1][2] = 1
graph[2][1] = 1
graph[1][3] = 5
graph[3][1] = 5
graph[2][3] = 2
graph[3][2] = 2
graph[2][4] = 8
graph[4][2] = 8
graph[3][4] = 2
graph[4][3] = 2
floyd()
for x in graph[1:]:
print(x[1:])
Reference
https://c4u-rdav.tistory.com/51
'CS' 카테고리의 다른 글
[CS] blocking, non-blocking, asynchronous I/O Model에 대한 나름의 이해 (0) | 2023.09.05 |
---|---|
[CS] 장기 중기 단기 스케줄러에 대한 나름의 이해 (0) | 2023.09.03 |
[CS][X] 프림 알고리즘 시간 복잡도에 대한 이해 (0) | 2023.08.20 |
[CS] 크루스칼 알고리즘 시간 복잡도에 대한 이해 (0) | 2023.08.20 |
[CS] DFS, BFS의 O(V+E)에 대한 이해 (0) | 2023.08.20 |