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

지금까지는 그래프의 노드간 이동 비용이 동일하다고 가정하에 진행했다.

하지만 가중치라는 값이 있어서 노드간 이동비용이 다를 수 있다. 

 

https://ddmix.blogspot.com

이렇게 가중치가 있는 경우에는 처음에는 C에서 D까지 가는 비용이 9인데 E를 거치면 6이 된다.

탐색 중에 더 짧은 경로를 발견할 수 있기 때문에 이럴 때마다 경로를 다시 설정해야 한다. 

그래서 다익스트라는 두가지 행동을 반복해서 최단경로를 찾는다.

1. 방문하지 않은 노드 중에 비용이 가장 적은 노드를 선택한다.

2. 해당 노드에서 특정한 노드로 가는 것을 고려해서 최소 비용을 갱신한다.

 

verticles.resize(6);
adjacent = vector<vector<int>>(6,vector<int>(6,-1));

adjacent[0][1] = 15;
adjacent[0][3] = 35;
adjacent[1][0] = 15;
...

연결되지 않은 정점은 -1로, 연결된 정점은 가중치를 부여한다.

 

void Dijikstra(int here)
{
	struct VertexCost
    {
	int vertex;
        int cost;
    };

    list<VertexCost> discovered;
    vector<int> best(6,INT_MAX); //정점별로 지금까지 발견한 최소 거리
    
    discovered.push_back(VertexCost{here,0});
    best[here] = 0;
    
    while(discovered.empty()==false)
    {
		//제일 좋은 후보 찾기
        list<VertexCost>::iterator bestIt;
        int bestCost = INT32_MAX;
        for(auto it = discovered.begin();it != discovered.end();++it)
        {        	
            if(it->cost < bestCost)
            {
        	bestCost = it->cost;
            	bestIt = it;
            }
        }
        int cost =  bestIt->cost;
        here = bestIt->vertex;
        discovered.erase(bestIt);
   //while loop 계속...

here과 연결된 정점들 (discovered) 중에 가장 가까운 정점을 골라 here로 설정한다.

이 코드를 우선순위 큐로 대체하면 훨씬 짧게 쓸 수도 있다. 속도도 훨씬 빠르다.

https://cppking.tistory.com/178

[백준] 1753번 - 다익스트라 최단경로

 

// 최적 경로 계산 시작! 이미 더 짧은 경로가 있다면 스킵.
		if (best[here] < cost)
			continue;

		// 방문!
		for (int there = 0; there < 6; there++)
		{
			// 연결되지 않았으면 스킵.
			if (adjacent[here][there] == -1)
				continue;

			// 더 좋은 경로를 과거에 찾았으면 스킵.
			int nextCost = best[here] + adjacent[here][there];
			if (nextCost >= best[there])
				continue;

			discovered.push_back(VertexCost{ there, nextCost });
			best[there] = nextCost;
			parent[there] = here;			
		}
  }//loop 끝

 

 

더 짧은 경로가 best[here]에 저장되어있다면 스킵한다.

중요한 부분인데 이것이 다익스트라 알고리즘에서 방문한 노드를 재방문하지 않게 한다.

dist배열에 노드를 방문한 후에  최단거리를 저장해 놓으므로 최단거리가 계산된 노드에 대해서 거리를

갱신하지 않는다는 것은 방문한 노드를 재방문하지 않는다는 것을 의미한다.

best[노드]가 INT_MAX가 아니면 최단거리인데, 왜냐하면 다익스트라 알고리즘이

그리디하게 현재 노드로부터 최단거리를 항상 갱신하기 때문이다.

그래서 한번 최단거리를 계산해서 best에 저장하고 그 후로 best보다 큰 값이 오면 continue로

스킵해서 한번 방문한 노드를 재방문하지 않는 것이다.

그 후 방문해서 인접정점들 중 더 좋은 경로를 찾으면 discovered에 집어넣는다.