[C++] 거의 최단 경로(Dijkstra) - 5719

다익스트라 알고리즘을 이용한 거의 최단 경로 구하기

다익스트라(Dijkstra) - O(E * logE)

다익스트라 알고리즘을 모른다면 위 글을 보고 오세욥

---

5719번: 거의 최단 경로

 

해결 방안

위 문제를 해결하기 위한 조건

1. 최단 경로에 포함되는 경로는 사용하면 안됨

2. 최소 비용이 드는 모든 경로 또한 사용하면 안됨

 

위의 조건을 만족하기 위해서는 당연하게도 목표 노드 까지의 최소비용을 미리 알고 있어야함

따라서 dijkstra알고리즘을 1회 실행시키는 것으로는 해결이 힘듦

 

그래서 우리는 첫번째 Dijkstra에서 최소 비용이 드는 모든 노드를 체크해주고

두번째 dijkstra에서 최단 경로에 포함되는 간선을 뺀 최소 비용, 즉 거의 최단 경로를 찾을거임

 

---

최단 경로 찾기

vector<vector<int>> parent(N + 1);

최단 경로를 체크하기 위해서 parent라는 2차원 vector를 만들어줌

'node[0] -> node[6]의 최단 경로'에서 "node[6]바로 이전의 노드"를 parent로 넣어주는거

 

그런데.. node[6]으로 가기 위한 최단 경로가 여러개일 수도 있기 때문에 벡터로 만들어준거임!

for (auto a : v[currNode])
{
    if (path[currNode][a.second]) continue;

    int nextNode = a.second;
    int nextDist = currDist + a.first;

    if (cost[nextNode] == nextDist)
    {
        parent[nextNode].push_back(currNode);
    }

    else if (cost[nextNode] > nextDist)
    {
        parent[nextNode].clear();
        parent[nextNode].push_back(currNode);

        cost[nextNode] = nextDist;
        pq.push(make_pair(-cost[nextNode], nextNode));
    }
}

최초 비용이 구해지면 parent를 비워줌! ( 이전에 찾은 경로는 최단 경로가 아닌게 되기 때문 )

같은 비용의 경로를 찾으면 parent에 추가해줌

 

이후 2차원 bool인 path에 지금까지 찾은 최단 경로를 추가해 주면 됨!

---

최단 경로 체크

- 깊이 우선 탐색

void addPath(vector<vector<int>>& parent, int curr)
{
	for (int pre : parent[curr])
	{
		if (path[pre][curr]) continue;
		path[pre][curr] = true;
		addPath(parent, pre);
	}
}

부모 노드와 현재 노드가 연결 되어 있다고 체크후

재귀 함수를 이용하여 부모 노드를 인자로 넘김

(이미 확인이 된 노드라면 continue를 해줘야함 안그럴시 메모리 초과 )

 

- 너비 우선 탐색

void addPath(vector<vector<int>> &parent)
{
	queue<int> q;
	q.push(D);

	while (!q.empty())
	{
		int child = q.front();
		q.pop();
		for (int pre : parent[child])
		{
			if (path[pre][child]) continue;
			path[pre][child] = true;
			q.push(pre);
		}
	}
}

재귀함수가 부담스러울때 사용하면 좋은 방법으로

queue를 이용하여 재귀하지 않고 반복문 안에서 모든 간선들을 체크

---

거의 최단 경로 구하기

위의 과정들이 종료된 후 다시한번 dijkstra를 실행하면 거의 최단 경로가 구해짐

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define edge pair<int, int>
#define MAX 500000001
using namespace std;

int N, M, S, D;

vector<vector<edge>> v;

bool path[501][501];
bool  isSecond = false;

// 너비 우선 탐색
void addPath(vector<vector<int>> &parent)
{
	queue<int> q;
	q.push(D);

	while (!q.empty())
	{
		int child = q.front();
		q.pop();
		for (int pre : parent[child])
		{
			if (path[pre][child]) continue;
			path[pre][child] = true;
			q.push(pre);
		}
	}
}

// 깊이 우선 탐색
void addPath2(vector<vector<int>>& parent, int curr)
{
	for (int pre : parent[curr])
	{
		if (path[pre][curr]) continue;
		path[pre][curr] = true;
		addPath2(parent, pre);
	}
}

// 다익스트라
int dijkstra()
{
	vector<int> cost(N + 1, MAX);
	vector<vector<int>> parent(N + 1);

	cost[S] = 0;
	priority_queue<edge> pq;
	pq.push(make_pair(0, S));

	while (!pq.empty())
	{
		int currNode = pq.top().second;
		int currDist = -pq.top().first;
		pq.pop();

		if (cost[currNode] < currDist) continue;


		for (auto a : v[currNode])
		{
			if (path[currNode][a.second]) continue;

			int nextNode = a.second;
			int nextDist = currDist + a.first;

			if (cost[nextNode] == nextDist)
			{
				parent[nextNode].push_back(currNode);
			}

			else if (cost[nextNode] > nextDist)
			{
				parent[nextNode].clear();
				parent[nextNode].push_back(currNode);

				cost[nextNode] = nextDist;
				pq.push(make_pair(-cost[nextNode], nextNode));
			}
		}
	}

	int result = cost[D];

	if (!isSecond) addPath(parent);
	if (result == MAX) result = -1;

	return result;
}

// 입력
bool input()
{
	v.clear();
	std::cin >> N >> M;
	if (N == 0 && M == 0) return false;

	isSecond = false;
	for (int i = 0; i < N; i++)
		fill(path[i], path[i] + N, false);

	std::cin >> S >> D;
	v = vector<vector<edge>>(N + 1);

	for (int i = 0; i < M; i++)
	{
		int s, d, c;
		std::cin >> s >> d >> c;
		v[s].push_back(make_pair(c, d));
	}
	return true;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	while (input())
	{

		// 최단 경로 탐색
		// 모든 최단 경로 지우기
		dijkstra();

		isSecond = true;
		// 거의 최단 경로 탐색
		cout << dijkstra() << '\n';
	}



	return 0;
}