DP를 사용한 한 노드에서 다른 나머지의 노드에 대한 최단경로 탐색 알고리즘.
단, 음의 경로가 있다면 사용할 수 없다.
void Dijkstra_Using_Heap()
{
priority_queue<pair<int, int>> PQ;
PQ.push(make_pair(0, Start));
Dist[Start] = 0;
while (PQ.empty() == 0)
{
int Cost = -PQ.top().first;
int Cur = PQ.top().second;
PQ.pop();
for (int i = 0; i < Vertex[Cur].size(); i++)
{
int Next = Vertex[Cur][i].first;
int nCost = Vertex[Cur][i].second;
if (Dist[Next] > Cost + nCost)
{
Dist[Next] = Cost + nCost;
PQ.push(make_pair(-Dist[Next], Next));
}
}
}
for (int i = 1; i <= V; i++)
{
if (Dist[i] == INF) cout << "INF" << endl;
else cout << Dist[i] << endl;
}
}
출처: https://yabmoons.tistory.com/364 [얍문's Coding World..]