최단경로 - 다익스트라 , 플로이드 알고리즘

최단 경로는 어떤 정점 A에서 정점 Z까지의 최단 경로란 A에서 Z까지의 경로 중 간선의 가중치의 합이 가장 작은 경로 입니다.

단일 출발점 최단 경로

- 단일 시작점에서 최단 경로 구하기 문제는 임의의 시작점을 1개 정하고 다른 노드들 사이의 최단 경로를 구하는데 사용.

- 노드 사이의 거리가 모두 양수인 경우, 가장 널리 사용하는 것 다익스트라 알고리즘

다익스트라 알고리즘

- 한 출발점에서 다른 모든 정점으로 최단 경로를 구하는 문제로 가중치를 갖는 간선은 없음.

모든 쌍 최단 경로

- 모든 정점쌍 간의 최단 경로를 구하는 방법, 경로의 길이가 음인 사이클이 그래프에 존재하지 않을 것을 가정, 단일 출발점으로

하여서 반복적으로 적용해 구할 수 있음.

O(|V|s)

- 경로의 길이가 음인 사이클이 그래프에 존재 X

- 플로이드 알고리즘 적용.

- 플로이드 알고리즘의 시간복잡도는 $O(V^3)$이다

 
//Floyd calculates shortest dist from all nodes to all nodes
 
/*
0. Initialize d with inf except adj nodes
1. Find d[s][e] by comparing current d[s][e] with d[s][m]+d[m][e]
*/
 
#include <stdio.h>
#define INF 1<<20
 
int d[1000][1000];
int n, m;
 
void Init()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if(i!=j) d[i][j] = INF; 
}
 
void Floyd()
{
    for (int m = 1; m <= n; m++) //가운데 노드
        for (int s = 1; s <= n; s++) //시작 노드
            for (int e = 1; e <= n; e++) //마지막 노드
                if (d[s][e] > d[s][m] + d[m][e])
                    d[s][e] = d[s][m] + d[m][e]; //가운데를 거쳐가는 것이 더 빠르면 그걸로 업데이트한다.
}
 
int main()
{
    scanf("%d %d", &n, &m); //n: 노드의 개수, m: 간선의 개수
    Init(); //d의 모든 값을 무한으로 초기화(단, d[i][i]는 0)
    for (int i = 0; i < m; i++) { //인접행렬 입력받기
        int x, y, c;
        scanf("%d %d %d", &x, &y, &c);
        d[x][y] = c;
    }
 
    Floyd();
 
    for (int i = 1; i <= n; i++) //모든 경로의 최단거리 출력
        for(int j=1; j<=n; j++)
            printf("Shortest dist from %d to %d: %d\n", i, j, d[i][j]);
}