[BOJ알고리즘, C++]#11404_플로이드, 플로이드-워셜, 최단 경로 알고리즘, 길 찾기 알고리즘

 

#0. 문제

 

 

---

 

#1. 풀이

 

1. 플로이드-워셜 알고리즘

[알고리즘]#2_길 찾기 알고리즘

 

[정의] : 플로이드-워셜 알고리즘은 음수 가중치를 포함하는 가중치 그래프의 '전체-쌍 최단 경로'를 구하는 알고리즘입니다.

[특징] : 플로이드-워셜 알고리즘은 DP와 세 개의 중첩 for 문을 통해 각 정점의 최단 경로 값을 구합니다.

[성능] : 플로이드-워셜 알고리즘의 평균, 최악 시간 복잡도는 항상 O(n³)입니다.

 

2. 시작 정점, 시작-도착을 잇는 경로 정점, 도착 정점

 

1. 첫 번째 for-문은 경로 정점을 순회합니다.
2. 두 번째 for-문은 시작 정점을 순회합니다.
3. 세 번째 for-문은 도착 정점을 순회합니다.
4. 세 개의 중첩 for-문을 순회하며, (시작 - 경로) + (경로 - 도착)의 값이 현재 (시작 - 도착) 최단 경로 값보다 작다면, 업데이트해 줍니다.

 

---

 

#3. 코드

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int n, m;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    cin >> m;
    
    // #1. 2차원 vector 형식의 그래프 선언
    vector<vector<int>> graph(n+1, vector<int>(n+1, 0));
    // #2. 그래프 구성
    while(m--)
    {
        int start, dest, weight;
        
        cin >> start >> dest >> weight;
        // 여러 노선 존재 가능, 최소 비용을 갖는 노선으로 갱신
        if(graph[start][dest] == 0 || graph[start][dest] > weight)
            graph[start][dest] = weight;
     }
     
     //#3. 플로이드-워셜 알고리즘(DP와 3번의 중첨 for-loop 활용)
    for(int k=1; k<=n; ++k)
    {
        for(int i=1; i<=n; ++i)
        {
            for(int j=1; j<=n; ++j)
            {
                if(graph[i][k] != 0 && graph[k][j] != 0
                  && (graph[i][j] == 0 || graph[i][j] > graph[i][k] + graph[k][j]))
                {
                    graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }
    
    // #4. 결과 출력
    for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<=n; ++j)
        {
            if(i == j)
                cout << 0 << ' ';
            else
                cout << graph[i][j] << ' ';
        }
        cout << '\n';
    }
    
    return 0;
}

 

---