가중치 방향 그래프(weighted directed graph)의 최단 경로 찾기

문제

가중치 방향 그래프(weighted directed graph)의 한 정점(vertex)에서 다른 정점으로 갈 수 있는 경로 중 가중치가 가장 작은 경로의 가중치를 구해보자

알고리즘[편집]

아래는 이 문제를 해결하기 위한 주요 알고리즘들이다.

• 데이크스트라 알고리즘 : 단일-쌍, 단일-출발, 단일-도착 최단 경로 문제를 풀 수 있다.
• 벨먼-포드 알고리즘 : 변의 가중치가 음수라면 단일 출발 문제를 풀 수 있다.
• A* 탐색 알고리즘 : 탐색 속도를 높히기 위한 휴리스틱 방법을 사용하며, 단일-쌍 최단 경로 문제를 풀 수 있다.
• 플로이드-와셜 알고리즘 : 전체-쌍 최단 경로 문제를 풀 수 있다.

출처 : wikipedia.org

---

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. 이 알고리즘은 플로이드 알고리즘이라고도 알려져 있다.

계산 복잡도[편집]

플로이드-워셜 알고리즘으로 모든 정점 간 경로의 최소비용을 구하는 것은 ${\displaystyle O(|V|^{3})}$의 시간 복잡도를 갖는다. 경유지를 기록한 경우, 경로를 역으로 추출하는 알고리즘의 복잡도는 ${\displaystyle O(|V|)}$의 시간 복잡도를 갖는다. 종종 데이크스트라 알고리즘과 자주 비교되곤 하는데, 두 알고리즘 모두 각각의 장단점이 있기 때문에 상황에 맞는 알고리즘 선정 필요성이 요구된다.

출처 : wikipedia.org

---

Consider a graph  with vertices  numbered 1 through . Further consider a function  that returns the shortest possible path from  to  using vertices only from the set  as intermediate points along the way. Now, given this function, our goal is to find the shortest path from each  to each  using only vertices in .

If ${\displaystyle w(i,j)}$ is the weight of the edge between vertices ${\displaystyle i}$ and ${\displaystyle j}$, we can define ${\displaystyle \mathrm {shortestPath} (i,j,k)}$ in terms of the following recursive formula: the base case is

${\displaystyle \mathrm {shortestPath} (i,j,0)=w(i,j)}$

and the recursive case is

${\displaystyle \mathrm {shortestPath} (i,j,k)=}$

${\displaystyle \mathrm {min} {\Big (}\mathrm {shortestPath} (i,j,k-1),}$

${\displaystyle \mathrm {shortestPath} (i,k,k-1)+\mathrm {shortestPath} (k,j,k-1){\Big )}}$.

This formula is the heart of the Floyd–Warshall algorithm. The algorithm works by first computing ${\displaystyle \mathrm {shortestPath} (i,j,k)}$ for all ${\displaystyle (i,j)}$ pairs for ${\displaystyle k=1}$, then ${\displaystyle k=2}$, etc. This process continues until ${\displaystyle k=N}$, and we have found the shortest path for all ${\displaystyle (i,j)}$ pairs using any intermediate vertices.

출처 : wikipedia.org

#include "stdafx.h"
#define N 4
#include <algorithm> //min 함수 
#include <iostream>
#include <iomanip> // setw 함수 
using namespace std;
 
void floyd(int W[][N]);
void printArray(const int W[][N]);
int main()
{
    int W[N][N] = { {0,INT_MAX,-2,INT_MAX }, {4,0,3,INT_MAX },{ INT_MAX ,INT_MAX ,0,2}, { INT_MAX ,-1,INT_MAX ,0} };
    printArray(W);
    cout << endl;
    floyd(W);
 
    return 0;
}
void floyd(int W[][N]) {
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                W[i][j] = min(W[i][j], W[i][k] == INT_MAX || W[k][j] == INT_MAX ? INT_MAX : W[i][k] + W[k][j]);
            }
        }
        printArray(W);
        cout << endl;
    }
}
void printArray(const int W[][N]) {
    //cout.setw(ios::right);//오른쪽 정렬
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (W[i][j] == INT_MAX) {
                cout << setw(3) << "∞";
            }
            else {
                cout << setw(3) << W[i][j];
            }
        }
        cout << endl;
    }
}
 

결과