■ 그래프에서 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)을 최단 경로를 구하는 방법을 보여준다.
▶ 예제 코드 (PY)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
import sys def getFloydWarshallShortestPathListList(nodeCount, adjacentListList): distanceListList = [[sys.maxsize] * nodeCount for _ in range(nodeCount)] for y, x, edge in adjacentListList: distanceListList[y - 1][x - 1] = edge for k in range(nodeCount): distanceListList[k][k] = 0 for y in range(nodeCount): for x in range(nodeCount): distanceListList[y][x] = min(distanceListList[y][x], distanceListList[y][k] + distanceListList[k][x]) return distanceListList nodeCount = 4 # 노드 수 adjacentListList = [[1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1]] # [1, 3, -2]는 node1에서 node3까지 edge가 -2이다. shortestPathListList = getFloydWarshallShortestPathListList(nodeCount, adjacentListList) print(shortestPathListList) """ [[0, -1, -2, 0], [4, 0, 2, 4], [5, 1, 0, 2], [3, -1, 1, 0]] ================================= node1 node2 node3 node4 ===== ===== ===== ===== ===== node1 0 -1 -2 0 node2 4 0 2 4 node3 5 1 0 2 node4 3 -1 1 0 ================================= """ |