플로이드 최단경로 알고리즘

플로이드 최단경로 알고리즘

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int P[5][5],D[5][5],W[5][5];
 
 
void floyd(int n) {
    int i, j, k;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            P[i][j] = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            D[i][j] = W[i][j];
    for(int k=0;k<n;k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (D[i][k] + D[k][j] < D[i][j]) {
                    P[i][j] = k;
                    D[i][j] = D[i][k] + D[k][j];
                }
}
void path(int q, int r) {
    if (P[q][r] != 0) {
        path(q, P[q][r]);
        cout << "v" << P[q][r] << " ";
        path(P[q][r], r);
    }
}
 
 
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> W[i][j];
    floyd(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cout << D[i][j]<<" ";
        cout << endl;
    }
    path(1, 0);
    cout << endl;
    path(2, 4);
 
 
    return 0;
}
 

오늘 알고리즘 수업시간에 배운 플로이드의 최단경로 알고리즘입니다. 

간선의 값을 입력할 때 100의 의미는 경로가 없다는 뜻입니다! 

path 1->0의 최단경로는 1->3->4->0으로 간다는 걸 path(1,0)을 통해서 알 수 있었습니다.