최단 거리 계산 - 다익스트라

다익스트라 알고리즘 

최단 경로를 구하는 알고리즘

임의의 시작 정점에서 각각의 정점으로의 최단 경로를 구해낸다.

프림 알고리즘과 유사하다.

프림 알고리즘과 같이 그리디 알고리즘 기반이다.

전체적인 흐름은

시작 정점을 지정하고 해당 정점으로 가는 간선을 우선순위 큐에 넣는다. 이 간선은 시작을 나타내는 간선으로 가중치는 0이고 출발지는 -1로 한다.

우선순위 큐가 빌때까지 반복 {

우큐에서 하나 뺌
우큐에서 하나 삭제

해당 간선이 방문했을 경우 다음 반복

해당 간선 방문으로 표시

그래프를 모두 확인하여 시작 정점에 붙은 간선을 확인하여 
거리가 현재 가중치보다 높게 저장된 간선을 현재 가중치로 계산하여 저장 후 우큐에 삽입

}

말로 보면 좀 힘들고 코드로 보는게 편할듯 하다..

 

int calDistance(int src, int dst) {
    vector<int> distance;
    vector<bool> visited;
    priority_queue<edge, vector<edge>, compare> pq;

    distance.resize(10, numeric_limits<int>::max());
    visited.resize(10, false);

    distance[src] = 0;

    edge a;
    a.from = -1;
    a.to = src;
    a.weight = 0;
    pq.push(a);
    

    while (!pq.empty()) {
        edge current = pq.top();
        pq.pop();

        if (visited[current.to])
            continue;

        visited[current.to] = true;

        for (edge info : graph) {
            if (info.from == current.to) {
                if (distance[info.to] > (distance[current.to] + info.weight)) {
                    distance[info.to] = (distance[current.to] + info.weight);

                    pq.push(info);
                }
            }
        }
    }

    return distance[dst];
}