[개념공부]Dijkstra Algorithm
📒Dijkstra Algorithm
✍Dijkstra Algorithm이란?
DP를 사용한 한 노드에서 다른 나머지의 노드에 대한 최단경로 탐색 알고리즘.
단, 음의 경로가 있다면 사용할 수 없다.
✍특징
📌특징
- 어떠한 경우에도 음의 경로가 존재하면 안된다.
- 기존에 구한 경로에 대한 가중치 값을 사용하기 때문에 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;
}
}
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..]
📌관련 문제
Author And Source
이 문제에 관하여([개념공부]Dijkstra Algorithm), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gomhyeok/개념공부Dijkstra-Algorithm저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)