[이코테]CHAPTER 09 최단 경로 알고리즘 - 플로이드워셜 알고리즘 - Python(파이썬),Java(자바)

참고자료 : https://www.youtube.com/watch?v=acqm9mM1P6o

📎 다익스트라(Dijkstra) 알고리즘과 플로이드 워셜(Floy-Warshall) 알고리즘의 차이

1) 다익스트라(Dijkstra) 알고리즘 

- 자세한 설명은 : https://coooco.tistory.com/36?category=1071114

- 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우에 사용하는 알고리즘

- 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택 -> 해당 노드를 거쳐가는 경로 확인 -> 최단 거리 테이블 갱신 

- 그리디 알고리즘

2) 플로이드 워셜(Floy-Warshall) 알고리즘

 - 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용하는 알고리즘

- 단계마다 거쳐가는 노드를 기준으로 알고리즘을 수행 -> 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드 찾을 필요 X

- 노드의 개수가 N개일 때, 알고리즘상으로 N번의 단계를 수행하며, 단계마다 O(N²)의 연산을 통해 '현재 노드를 거쳐가는' 모든 경로를 고려 -> 시간 복잡도 : O(N³)

시간 복잡도 추가 설명

노드의 개수를 N이라고 할 때, 1부터 N까지의 노드는 모두 경유 노드가 가능하다.

경유 노드를 제외한 (N-1)개의 노드 중 두개를 골라 시작노드,도착노드라고 가정해보자. 

이 경우를 구하는 가지수: (N-1)P2로 계산하여 O(N²)의 시간복잡도에 경유 노드마다 반복해야하믈 시간복잡도 O(N³)이 된다.

- 다이나믹 프로그래밍 (노드의 개수가 N이라고 할 때, N번만큼의 단계를 반복하며 점화식에 맞게 2차원 리스트를 갱신하기 때문) 

- 시간 복잡도가 O(N³)이므로 노드,간선의 개수가 적은 경우에만 사용할 수 있으며 노드,간선의 개수가 많은 경우에는 다익스트라 알고리즘을 사용

📌 플로이드 워셜 알고리즘 점화식

Dab = min(Dab,Dak+Dkb)

- a에서 b로 가는 거리(Dab)는 기존에 a에서 b로 가는 최단 거리(Dab)와 (a에서 k로 가는 거리(Dak)+ k에서 b로 가는 최단 거리(Dkb) 비교해서 더 작은 값으로 갱신

📌 플로이드 워셜 알고리즘 동작 과정

이렇게 연결된 노드들이 있다고 가정하면 먼저 주어진 노드들을 최단 거리 테이블에 작성한다

1번 노드를 경로노드라고 가정하였을 때 나오는 경우의 수는 3P2 = 6가지로 앞서 계산한 최단 거리와 비교하여서 최단 거리 테이블을 갱신한다.

2번 노드를 경로노드라고 가정하였을 때 나오는 경우의 수는 3P2 = 6가지로 앞서 계산한 최단 거리와 비교하여서 최단 거리 테이블을 갱신한다.

 

3번 노드를 경로노드라고 가정하였을 때 나오는 경우의 수는 3P2 = 6가지로 앞서 계산한 최단 거리와 비교하여서 최단 거리 테이블을 갱신한다.

4번 노드를 경로노드라고 가정하였을 때 나오는 경우의 수는 3P2 = 6가지로 앞서 계산한 최단 거리와 비교하여서 최단 거리 테이블을 갱신한다.

🖥 코드 구현

입력	출력
4 (노드의 개수) 7 (간선의 개수) 1 2 4 (1번 노드에서 4번 노드로 가는 비용 : 4 ) 1 4 6 2 1 3 2 3 7 3 1 5 3 4 4 4 3 2	4 (노드의 개수) 7 (간선의 개수) 1 2 4 (1번 노드에서 4번 노드로 가는 비용 : 4 ) 1 4 6 2 1 3 2 3 7 3 1 5 3 4 4 4 3 2

💻Python(파이썬)

import sys

INF = int(1e9)

#노드의 개수 및 간선의 개수 입력 받기
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
#2차원 리스트를 만들고, 무한으로 초기화
graph = [[INF]*(n+1) for _ in range(n+1)]

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

#각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(m):
    #A에서 B로 가는 비용이 C
    a,b,c = map(int,sys.stdin.readline().split())
    graph[a][b]=c

#경로 노드
for k in range(1,n+1):
    #시작 노드
    for a in range(1,n+1):
        #도착 노드
        for b in range(1,n+1):
            graph[a][b]=min(graph[a][b],graph[a][k]+graph[k][b])

for a in range(1,n+1):
    for b in range(1,n+1):
        if graph[a][b]==INF:
            print(-1,end=" ")
        else:
            print(graph[a][b],end=" ")
    print()

💻Java(자바)

package s15_shortest;

import java.util.*;
import java.io.*;

public class e01_9_3 {
    public static final int INF = (int)1e9;
    public static int n,m;
    public static int[][] graph = new int[501][501];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //노드의 개수
        int n = Integer.parseInt(br.readLine());
        //간선의 개수
        int m = Integer.parseInt(br.readLine());
        for(int i=0;i<501;i++){
            Arrays.fill(graph[i],INF);
        }
        for(int i=1;i<=n;i++){
            graph[i][i]=0;
        }
        for(int i=0;i<m;i++){
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            graph[a][b]=c;
        }
        //점화식에 따라 플로이드 워셜 알고리즘 수행
        for(int k=1;k<=n;k++){
            for(int a=1;a<=n;a++){
                for(int b =1;b<=n;b++){
                    graph[a][b]=Math.min(graph[a][b],graph[a][k]+graph[k][b]);
                }
            }
        }
        //수행된 결과를 출력
        for(int a=1;a<=n;a++){
            for(int b=1;b<=n;b++){
                if(graph[a][b]==INF){
                    System.out.print(-1+" ");
                }
                else
                    System.out.print(graph[a][b]+" ");
            }
            System.out.println();
        }
    }
}