플로이드 워셜(Floyd Warshall) 알고리즘

[ Floyd Warshall ]

Floyd Warshall 알고리즘은 모든 노드에서 모든 노드까지의 최단 경로를 구할 수 있는 알고리즘이다.

• 시간 복잡도 = O(N^3)
• 가중치가 음수인 Edge가 존재할 때도 적용 가능
• 음수 Cycle 감지

N(Node의 수)

[ 알고리즘 ]

• 그래프 연결 정보를 가지고 distance[src][dst]를 초기화해준다.
  distance[src][dst]

  	A	B	C	D	E
  A	0	4	3	INF	INF
  B	INF	0	INF	1	INF
  C	INF	6	0	4	INF
  D	INF	INF	INF	0	2
  E	10	INF	INF	INF	0

• 모든 노드를 순회하여 거쳐갈 노드(middle)를 지정한다.

  • 나머지 모든 노드를 순회하여 출발 노드(src)를 지정한다.

    • 나머지 모든 노드를 순회하여 도착 노드(dst)를 지정한다.
      middle을 거쳐서 가는 경우가 distance[src][dst]보다 작다면 업데이트해 준다.

과정

[ 코드 ]

for middle in range(1, N + 1):
    for src in range(1, N + 1):
        for dst in range(1, N + 1):
            if(src == dst):
                continue
            new_cost = load_map[src][middle] + load_map[middle][dst]
            if(new_cost < load_map[src][dst]):
                load_map[src][dst] = new_cost