인접 리스트 기반 다익스트라 최단 경로 알고리즘

인접 리스트(adjacency list)로 표현된 그래프 G(V, E)와 시작 정점(source vertex)이 주어졌을 때, 다익스트라(Dijkstra) 알고리즘은 시작 정점에서 그래프의 다른 모든 정점까지 도달하는 최소 비용의 최단 경로를 찾아냅니다.

해결 접근 방법

이 문제를 해결하기 위해 두 개의 리스트를 활용합니다. 하나는 최단 경로 트리(shortest path tree)에 이미 확정된 정점들을 보관하는 리스트이며, 다른 하나는 아직 확정되지 않은 정점들을 담는 리스트입니다. 알고리즘의 매 단계마다 아직 처리되지 않은 정점 중에서 시작 정점으로부터의 거리가 가장 짧은 정점을 선택하게 됩니다.

또한 각 정점의 선행 노드(predecessor node)를 저장하기 위한 별도의 리스트를 사용합니다. 이 선행 노드 정보를 따라가면 시작 정점에서 목적지 정점까지의 실제 경로를 역추적하여 복원할 수 있습니다.

그래프를 인접 리스트로 표현할 경우, 다익스트라 최단 경로 알고리즘의 시간 복잡도는 O(E log V)입니다. 여기서 E는 간선(edge)의 개수, V는 정점(vertex)의 개수를 의미합니다. 참고로 우선순위 큐(priority queue)나 최소 힙(min-heap)을 함께 사용하면 '최소 거리 정점 선택' 과정을 더욱 효율적으로 처리할 수 있습니다.

입력 및 출력

입력:
각 간선의 비용이 포함된 그래프의 인접 리스트

출력:
0 to 1, Cost: 3 Previous: 0
0 to 2, Cost: 5 Previous: 1
0 to 3, Cost: 4 Previous: 1
0 to 4, Cost: 6 Previous: 3
0 to 5, Cost: 7 Previous: 2
0 to 6, Cost: 7 Previous: 4

알고리즘

dijkstraShortestPath(g : Graph, dist, prev, start : node)

입력 − 그래프 g, 각 정점까지의 거리를 저장할 dist 리스트, 선행 노드를 저장할 prev 리스트, 시작 정점(start)

출력 − 시작 정점에서 나머지 모든 정점까지의 최단 경로

Begin
    for all vertices u in (V - start) do
        dist[u] := ∞
        prev[u] := φ
    done

    set dist[start] = 0 and prev[start] := φ;

    for all node u in V do
        insert u into queue 'Q'.
    done

    while Q is not empty do
        u := minimum element from Queue
        delete u from Q
        insert u into set S

        for each node v adjacent with node u do
            if dist[u]+cost(v) < dist[v] then
                dist[v] := dist[u]+cost(v)
                prev[v] := u
            done
        done
    done
End

C++ 구현 예제

#include<iostream>
#include<set>
#include<list>
#include<algorithm>
using namespace std;

typedef struct nodes {
    int dest;
    int cost;
}node;

class Graph {
    int n;
    list<node> *adjList;
    private:
        void showList(int src, list<node> lt) {
            list<node> :: iterator i;
            node tempNode;

            for(i = lt.begin(); i != lt.end(); i++) {
                tempNode = *i;
                cout << "(" << src << ")---("<<tempNode.dest << "|"<<tempNode.cost<<") ";
            }
            cout << endl;
        }
    public:
        Graph() {
            n = 0;
        }

        Graph(int nodeCount) {
            n = nodeCount;
            adjList = new list<node>[n];
        }

        void addEdge(int source, int dest, int cost) {
            node newNode;
            newNode.dest = dest;
            newNode.cost = cost;
            adjList[source].push_back(newNode);
        }

        void displayEdges() {
            for(int i = 0; i<n; i++) {
                list<node> tempList = adjList[i];
                showList(i, tempList);
            }
        }

        friend void dijkstra(Graph g, int *dist, int *prev, int start);
};

void dijkstra(Graph g, int *dist, int *prev, int start) {
    int n = g.n;

    for(int u = 0; u<n; u++) {
        dist[u] = 9999;   //set as infinity
        prev[u] = -1;     //undefined previous
    }

    dist[start] = 0;   //distance of start is 0
    set<int> S;        //create empty set S
    list<int> Q;

    for(int u = 0; u<n; u++) {
        Q.push_back(u);     //add each node into queue
    }

    while(!Q.empty()) {
        list<int> :: iterator i;
        i = min_element(Q.begin(), Q.end());
        int u = *i; //the minimum element from queue
        Q.remove(u);
        S.insert(u); //add u in the set
        list<node> :: iterator it;

        for(it = g.adjList[u].begin(); it != g.adjList[u].end();it++) {
            if((dist[u]+(it->cost)) < dist[it->dest]) { //relax (u,v)
                dist[it->dest] = (dist[u]+(it->cost));
                prev[it->dest] = u;
            }
        }
    }
}

main() {
    int n = 7;
    Graph g(n);
    int dist[n], prev[n];
    int start = 0;

    g.addEdge(0, 1, 3);
    g.addEdge(0, 2, 6);
    g.addEdge(1, 0, 3);
    g.addEdge(1, 2, 2);
    g.addEdge(1, 3, 1);
    g.addEdge(2, 1, 6);
    g.addEdge(2, 1, 2);
    g.addEdge(2, 3, 1);
    g.addEdge(2, 4, 4);

    g.addEdge(2, 5, 2);
    g.addEdge(3, 1, 1);
    g.addEdge(3, 2, 1);
    g.addEdge(3, 4, 2);
    g.addEdge(3, 6, 4);
    g.addEdge(4, 2, 4);
    g.addEdge(4, 3, 2);
    g.addEdge(4, 5, 2);
    g.addEdge(4, 6, 1);
    g.addEdge(5, 2, 2);
    g.addEdge(5, 4, 2);
    g.addEdge(5, 6, 1);
    g.addEdge(6, 3, 4);
    g.addEdge(6, 4, 1);
    g.addEdge(6, 5, 1);

    dijkstra(g, dist, prev, start);

    for(int i = 0; i<n; i++)
        if(i != start)
            cout<<start<<" to "<<i<<", Cost: "<<dist[i]<<" Previous: "<<prev[i]<<endl;
}

실행 결과

0 to 1, Cost: 3 Previous: 0
0 to 2, Cost: 5 Previous: 1
0 to 3, Cost: 4 Previous: 1
0 to 4, Cost: 6 Previous: 3
0 to 5, Cost: 7 Previous: 2
0 to 6, Cost: 7 Previous: 4

실행 결과에는 시작 정점 0에서 각 정점까지의 최소 비용(dist)과 해당 정점 바로 앞에 위치한 선행 노드(prev)가 함께 출력됩니다. 예를 들어 정점 6까지의 최단 경로 비용은 7이며, 선행 노드 정보를 역추적하면 0 → 1 → 3 → 4 → 6 순서의 경로임을 확인할 수 있습니다.