[Algorithm] 다익스트라 알고리즘

도착지 까지 최단 거리를 구하는 다익스트라 알고리즘이다.

greedy알고리즘을 통해 구하고 수학적 귀납법을 통해 증명 가능하다.

 

"가정이 방문한 꼭짓점이 n-1일 때 성립한다고 가정하자. 이 경우에, 모든 미방문 꼭짓점에서 dist[u]가 가장 작은 u에 대해서 dist[u] = dist[v] + length[v,u]을 만족하는 변 vu를 선택한다. dist[u]는 source에서 u까지의 가장 짧은 거리로 볼 수 있다. 만약 그 경로보다 더 짧은 경로가 있고, 그 경로의 첫 번째 미방문 꼭짓점을 w라고 한다면 처음의 가정인 dist[w] > dist[u]에 의해서 모순이 생긴다. 이와 비슷하게, u로 가는 경로 중 미방문 꼭짓점을 지나지 않는 더 짧은 경로가 있고, 그 경로의 마지막 꼭짓점이 w라고 한다면, dist[u] = dist[w] + length[w,u]이여야 하기 때문에 여전히 모순이 생긴다."

 

우선순위 큐를 사용하지 않을 경우  O(V^2)의 복잡도를 가지며(E:edge, V:vertex)

우선순위 큐를 사용할 경우 O(E+VlogV)의 복잡도를 가진다

 

#define VERTEX_MAX 50
#define INF 2123456789
 
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
 
struct cmp {
    bool operator()(pair<int, int> a, pair<int, int> b)//우선순위큐 우선순위 정의해주는 함수
    {
        if (a.second > b.second)
            return 1;
        else
        {
            return 0;
        }
    }
};
 
priority_queue<int,vector<pair<int,int>>,cmp> gMyPriorityQueue;
vector<pair<int, int>> gVertex[VERTEX_MAX];
 
int gDistance[VERTEX_MAX];
bool gIsVisited[VERTEX_MAX];//우선순위 큐로 할땐 방문체크 안한다.
int gStartVertex;
int gVertexCount;
int gEdgeCount;
 
void fileInput(void);
void printDistance(int* distnace);
void printGraph(vector<pair<int, int>>* vertex);
 
 
void fileInput(void)
{
    int tempStartVertex = 0;
    int tempEndVertex = 0;
    int tempWeight = 0;
    ifstream inputFile("graph_input.txt");
    
    inputFile >> gVertexCount;
    inputFile >> gEdgeCount;
    inputFile >> gStartVertex;
 
    for (int i = 0; i < gEdgeCount; i++)
    {
        inputFile >> tempStartVertex;
        inputFile >> tempEndVertex;
        inputFile >> tempWeight;
        gVertex[tempStartVertex].push_back(make_pair(tempEndVertex, tempWeight));        
    }
 
}
 
void printDistance(int* distance)
{
    cout << "distance:" << endl;
    for (int i = 1; i < gVertexCount + 1; i++)
    {
        cout << "d[" << i << "] = " << distance[i] << endl;
    }
}
 
void printGraph(vector<pair<int, int>> *vertex)
{
    cout << "vertex:" << endl;
    for (int i = 1; i < gVertexCount+1; i++)
    {
        cout << "[" << i << "]";
        for (vector<pair<int, int>>::iterator iter = vertex[i].begin(); iter != vertex[i].end(); ++iter)
        {
            cout << "->";
            cout << (*iter).first << "|" << (*iter).second;
        }
        cout << endl;
    }
}
 
void initGlobals(void)
{
    for (int i = 0; i < gVertexCount+1; i++)
    {
        gDistance[i] = INF;
    }
}
 
void dijkstra(int startVertex)
{
    initGlobals();
    vector<pair<int, int>>::iterator edgeIter = gVertex[startVertex].begin();
    gDistance[startVertex] = 0;//자기자신의 weight =0
 
    for (int vertexIndex = 1; vertexIndex < gVertexCount + 1; vertexIndex++)//시작점과 연결된 edge를 넣어준다.
    {
        gMyPriorityQueue.push(make_pair(vertexIndex, gDistance[vertexIndex]));
    }
 
    while (gMyPriorityQueue.empty() == false)
    {
        printDistance(gDistance);
        int currentVertex = 0;
        pair<int, int> connectedEdge = make_pair(0, 0);
        if (gDistance[gMyPriorityQueue.top().first] < gMyPriorityQueue.top().second)//오래된 edge들 pop해주는 코드
        {
            gMyPriorityQueue.pop();
            continue;
        }
        currentVertex = gMyPriorityQueue.top().first;
        gMyPriorityQueue.pop();
        for (edgeIter = gVertex[currentVertex].begin(); edgeIter != gVertex[currentVertex].end();++edgeIter)
        {
            connectedEdge = (*edgeIter);
            if (gDistance[currentVertex] + connectedEdge.second < gDistance[connectedEdge.first])
            {
                gDistance[connectedEdge.first] = gDistance[currentVertex] + connectedEdge.second;
                gMyPriorityQueue.push(make_pair(connectedEdge.first, gDistance[connectedEdge.first]));
            }
            else
            {
                continue;
            }
        }
    }
}
 
int main(void)
{
    fileInput();
    printGraph(gVertex);
    dijkstra(gStartVertex);
    printDistance(gDistance);
}