자료구조 - 최단경로 알고리즘

[최단경로 알고리즘 (Shortest Path Algorithm)]

 

• 목표: 두 정점 사이의 최단 경로를 찾는 것입니다. 이는 주로 경로 탐색, 네트워크 라우팅, GPS 경로 탐색 등에서 사용됩니다.
• 대표적인 예시: 다익스트라 알고리즘(Dijkstra's Algorithm), 벨만-포드 알고리즘(Bellman-Ford Algorithm), 플로이드-와샬 알고리즘(Floyd-Warshall Algorithm) 등이 있습니다.
• 특징: 그래프에서 간선의 가중치를 고려하여 시작 정점으로부터 목표 정점까지의 최단 경로를 찾습니다.

 

 

최소비용 알고리즘과 최단거리 알고리즘의 차이점

 

 

• 목표: 최소비용 알고리즘은 모든 정점을 연결하는데 필요한 최소 비용을 찾는 것에 중점을 두고 있으며, 최단거리 알고리즘은 특정 두 정점 사이의 최단 경로를 찾는 것에 중점을 둡니다.
• 응용 분야: 최소비용 알고리즘은 네트워크 구축 및 설계와 관련된 문제에 주로 사용되고, 최단거리 알고리즘은 경로 탐색 및 네트워크 라우팅과 같은 문제에 사용됩니다.
• 알고리즘 종류: 두 알고리즘은 서로 다른 알고리즘을 사용합니다. 최소비용 알고리즘에서는 주로 크루스칼 알고리즘 또는 프림 알고리즘을 사용하고, 최단거리 알고리즘에서는 다익스트라 알고리즘, 벨만-포드 알고리즘 또는 플로이드 알고리즘을 사용합니다.

 

요약하면, 최소비용 알고리즘은 그래프에서 모든 정점을 연결하는 최소 비용의 트리를 찾는 반면, 최단거리 알고리즘은 두 정점 사이의 최단 경로를 찾는 데 사용됩니다.

 

 

 

 

[최단 경로 알고리즘 방법]

 

1. 다익스트라 알고리즘 (Dijkstra's Algorithm)

• 목표: 주어진 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾습니다.
• 동작 방식: 시작 정점에서부터 출발하여 가장 가까운 정점을 선택하고, 선택된 정점을 경유하여 다른 정점까지의 최단 경로를 계산합니다.
• 특징: 음의 가중치가 없는 그래프에서 사용되며, 우선순위 큐를 이용하여 구현할 수 있습니다.
• 시간 복잡도: O((V + E) log V) 또는 O(V^2) // 우선순위 큐를 사용하는 경우와 사용하지 않는 경우

 

다익스트라 알고리즘의 의사 코드

다익스트라(그래프 G, 시작 정점 s):
    dist 배열 초기화: 모든 정점의 최단 거리를 무한대(INF)로 설정하고, 시작 정점의 거리는 0으로 설정
    우선순위 큐 Q에 시작 정점과 해당 정점까지의 거리를 삽입
    
    while Q가 비어있지 않은 동안:
        현재 정점을 Q에서 추출
        현재 정점에 인접한 모든 정점들에 대해:
            인접 정점의 거리를 갱신: dist[인접 정점] = min(dist[인접 정점], dist[현재 정점] + 인접 정점까지의 거리)
            갱신된 거리를 우선순위 큐에 삽입
            
    dist 배열 반환

 

 

 

 

다익스트라 알고리즘 코드

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

class DijkstraSP 
{
    public:
        DijkstraSP(int V) : V(V) {}

        // 시작 정점에서 모든 정점까지의 최단 경로를 계산하는 함수
        void shortestPath(const std::vector<std::vector<int>>& graph, int src) 
        {
            std::vector<int> dist(V, INT_MAX); // 시작 정점부터의 거리를 저장하는 배열
            std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;

            dist[src] = 0; // 시작 정점의 거리는 0

            pq.push({0, src});

            while (!pq.empty()) 
            {
                int u = pq.top().second;
                pq.pop();

                for (int v = 0; v < V; ++v) 
                {
                    if (graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
                    {
                        dist[v] = dist[u] + graph[u][v];
                        pq.push({dist[v], v});
                    }
                }
            }

            // 결과 출력
            std::cout << "Shortest distances from vertex " << src << ":\n";
            for (int i = 0; i < V; ++i) 
            {
                std::cout << "Vertex " << i << ": " << dist[i] << std::endl;
            }
        }

    private:
        int V; // 정점의 수
};

int main() 
{
    int V = 5; // 정점의 수
    std::vector<std::vector<int>> graph =
    {
        {0, 4, 0, 0, 0},
        {4, 0, 8, 0, 0},
        {0, 8, 0, 7, 0},
        {0, 0, 7, 0, 9},
        {0, 0, 0, 9, 0}
    };

    DijkstraSP sp(V);
    sp.shortestPath(graph, 0); // 시작 정점은 0번 정점으로 설정

    return 0;
}

 

 

2. 플로이드-와샬 알고리즘 (Floyd-Warshall Algorithm)

• 목표: 모든 정점 사이의 최단 경로를 찾습니다.
• 동작 방식: 모든 정점을 순회하면서 중간 정점을 경유하여 최단 경로를 계산합니다.
• 특징: 음의 가중치가 있어도 동작하며, 모든 정점 쌍에 대한 최단 경로를 찾습니다.
• 시간 복잡도: O(V^3)

 

플로이드-와샬 알고리즘의 의사코드

플로이드-와샬(그래프 G):
    dist 배열 초기화: dist[i][j]는 정점 i에서 정점 j까지의 최단 거리로 초기화
    모든 정점 쌍 (i, j)에 대해:
        - 정점 i에서 정점 j로의 직접적인 간선이 있으면 dist[i][j] = 간선의 가중치
        - 없으면 dist[i][j] = 무한대(INF)로 초기화
        
    모든 경유지 k에 대해:
        모든 정점 쌍 (i, j)에 대해:
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
            
    dist 배열 반환

 

 

 

플로이드-와샬 알고리즘 코드

#include <iostream>
#include <vector>
#include <climits>

class FloydWarshallSP
{
    public:
        FloydWarshallSP(int V) : V(V) {}

        // 모든 정점 사이의 최단 경로를 계산하는 함수
        void shortestPath(const std::vector<std::vector<int>>& graph) 
        {
            std::vector<std::vector<int>> dist = graph;

            // 경유지를 순회하면서 최단 경로 갱신
            for (int k = 0; k < V; ++k) 
           {
                for (int i = 0; i < V; ++i) 
                {
                    for (int j = 0; j < V; ++j) 
                    {
                        if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][k] + dist[k][j] < dist[i][j]) 
                        {
                            dist[i][j] = dist[i][k] + dist[k][j];
                        }
                    }
                }
            }

            // 결과 출력
            std::cout << "Shortest distances between all pairs of vertices:\n";
            for (int i = 0; i < V; ++i)
            {
                for (int j = 0; j < V; ++j) 
                {
                    if (dist[i][j] == INT_MAX)
                        std::cout << "INF ";
                    else
                        std::cout << dist[i][j] << " ";
                }
                std::cout << std::endl;
            }
        }

    private:
        int V; // 정점의 수
};

int main() 
{
    int V = 4; // 정점의 수
    std::vector<std::vector<int>> graph =
    {
        {0, 3, INT_MAX, 5},
        {2, 0, INT_MAX, 4},
        {INT_MAX, 1, 0, INT_MAX},
        {INT_MAX, INT_MAX, 2, 0}
    };

    FloydWarshallSP sp(V);
    sp.shortestPath(graph);

    return 0;
}