최단경로 찾기) 다익스트라 알고리즘

https://namu.wiki/w/%EC%97%90%EC%B8%A0%ED%97%88%EB%A5%B4%20%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC

 

다익스트라 알고리즘이란 그래프 자료구조에서 노드와 가중치가 있는 간선이 존재하고,

시작 노드에서 모든 노드까지의 최단 경로(최소 비용)를 구하는 알고리즘 이다.

 

매순간마다 갈 수 있는 노드 중 최소비용만 선택한다고 생각하면 된다. 

 

그래프) 노드, 간선이 존재하고 (방향그래프/ 무방향그래프, 연결그래프/비연결그래프)등으로 나눌 수 있다. 

 

 

• 시작 노드는 거리 0으로 설정.
• 모든 노드에 대해 거리 정보를 저장 (처음엔 무한대).
• 방문하지 않은 노드 중 거리 가장 짧은 것 선택
• 그 노드와 연결된 다른 노드들까지의 거리 업데이트 
• 모든 노드를 방문할 때까지 반복

 

#include <iostream>
#include <stack>
//#include <queue>

// : 다음 구조로 생성
//               [3]------3------[5]      
//                |              / \      
//                |             /   \     
//                4            3     4    
//                |           /       \   
//                |          /         \  
// [1]-----2-----[2]---1---[4]         [8]
//   \                       \         /  
//    \                       \       /   
//     3                       2     4    
//      \                       \   /     
//       \                       \ /      
//       [6]----------6----------[7]   

#define I	100
#define NUM_NODE	8
int edgeCost[NUM_NODE][NUM_NODE] =
{
	{ 0,2,I,I,I,3,I,I },//1
	{ 2,0,4,1,I,I,I,I },//2
	{ I,4,0,I,3,I,I,I },//3
	{ I,1,I,0,3,I,2,I },//4
	{ I,I,3,3,0,I,I,4 },//5
	{ 3,I,I,I,I,0,6,I },//6
	{ I,I,I,2,I,6,0,4 },//7
	{ I,I,I,I,4,I,4,0 },//8
};

using namespace std;

void FindPath(int startNode, int destNode, int* currCost, int* prevNode)
{
	currCost[startNode - 1] = 0;
	bool isVisited[NUM_NODE] = { 0, };

	for (int i = 0; i < NUM_NODE; i++)
	{
		int minIndex = -1;
		int minCost = I;

		for (int j = 0; j < NUM_NODE; j++)
		{
			if (isVisited[j] == true)	continue;

			if (minCost > currCost[j])
			{
				minCost = currCost[j];
				minIndex = j;
			}
		}
		isVisited[minIndex] = true;
		cout << "최소 비용 인덱스 : " << minIndex + 1 << endl;

		for(int j = 0; j < NUM_NODE; j++)
		{
			if (j == minIndex) continue;

			if (currCost[j] >
				currCost[minIndex] + edgeCost[minIndex][j])
			{
				currCost[j] = currCost[minIndex] + edgeCost[minIndex][j];
				prevNode[j] = minIndex;
			}
		}
	}
}

void PrintPath(const int* prevNode, int startNode, int destNode)
{
	stack<int> path;
	int current = destNode - 1;

	while (current != startNode - 1)
	{
		path.push(current + 1);
		current = prevNode[current];
	}
	path.push(startNode);

	while (!path.empty())
	{
		cout << path.top();
		path.pop();
		if (!path.empty())
			cout << "->";
	}
	cout << endl;
}

int main()
{
	int prevNode[NUM_NODE] = { -1, -1, -1, -1, -1, -1, -1, -1 };
	int currCost[NUM_NODE] = { I, I, I, I, I, I, I, I };

	int startNode, destNode;
	cout << "시작 위치를 입력하세요 : ";
	cin >> startNode;
	cout << "도착 위치를 입력하세요 : ";
	cin >> destNode;

	// 경로 탐색 알고리즘
	FindPath(startNode, destNode, currCost, prevNode);

	// 경로 출력
	PrintPath(prevNode, startNode, destNode);

}

 

실습때 진행한 코드는 우선순위큐를 배우지 않은 상태에서 작성한 코드라 직관성이 조금 떨어지고 어려울 수 있다. 

 

우선순위 큐를 적용해서 개선해보자. 

void FindPath(int startNode, int destNode, int* currCost, int* prevNode)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({ 0, startNode - 1 });
    currCost[startNode - 1] = 0;

    while (!pq.empty())
    {
        auto [cost, now] = pq.top(); pq.pop();

        // 이미 더 짧은 경로로 방문했다면 무시
        if (currCost[now] < cost) continue;

        for (int next = 0; next < NUM_NODE; ++next)
        {
            if (edgeCost[now][next] == I) continue;

            int newCost = currCost[now] + edgeCost[now][next];
            if (newCost < currCost[next])
            {
                currCost[next] = newCost;
                prevNode[next] = now;
                pq.push({ newCost, next });
            }
        }
    }
}

 

시간복잡도가 N^2에서 N logN으로 줄었다.