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

다익스트라가 처음이라면..

다익스트라(Dijkstra) - O(n^2)

---

 

다익스트라 문제를 E* logE로 해결하기 위해서는

정점(V)에 초점을 두는 것이 아니라 간선(E)에 초점을 두고 코딩을 해야함

int MAX = 1000000000;
int cost[8]; // 각 정점으로의 최소비용을 담을 예정
vector<pair<int, int>> vec[8];

int main()
{
	fill(cost, cost + 8, MAX); // 비용을 MAX로 초기화
    
	// first에 가중치 값을, second에 정점 번호를 넣음
	vec[0].push_back(make_pair(2, 2));
	vec[0].push_back(make_pair(1, 3));
	vec[0].push_back(make_pair(1, 4));

	vec[1].push_back(make_pair(2, 1));
	vec[1].push_back(make_pair(2, 4));
	vec[1].push_back(make_pair(4, 5));
	vec[1].push_back(make_pair(5, 8));

	vec[2].push_back(make_pair(1, 1));
	vec[2].push_back(make_pair(2, 4));
	vec[2].push_back(make_pair(1, 6));

	vec[3].push_back(make_pair(1, 1));
	vec[3].push_back(make_pair(2, 2));
	vec[3].push_back(make_pair(2, 3));
	vec[3].push_back(make_pair(1, 5));
	vec[3].push_back(make_pair(3, 6));
	vec[3].push_back(make_pair(2, 7));

	vec[4].push_back(make_pair(4, 2));
	vec[4].push_back(make_pair(1, 4));
	vec[4].push_back(make_pair(2, 7));
	vec[4].push_back(make_pair(3, 8));

	vec[5].push_back(make_pair(1, 3));
	vec[5].push_back(make_pair(3, 4));
	vec[5].push_back(make_pair(1, 7));

	vec[6].push_back(make_pair(2, 4));
	vec[6].push_back(make_pair(2, 5));
	vec[6].push_back(make_pair(1, 6));
	vec[6].push_back(make_pair(2, 8));

	vec[7].push_back(make_pair(5, 2));
	vec[7].push_back(make_pair(3, 5));
	vec[7].push_back(make_pair(2, 7));
   
}

위와 같이 모든 간선 정보를 v에 넣어두는 방식을 사용함

 

void dijkstra(int start)
{
	// 자기 자신으로 가는 비용을 0으로
	cost[start] = 0;

	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, start)); // 출발 지점과 그 비용을 넣음

	while (!pq.empty())
	{
		// 가중치가 가장 작은 노드의 index와 가중치를 꺼냄
		int current = pq.top().second;
		int dist = -pq.top().first; // min Heap으로 만들기 위해서 -를 붙임
		pq.pop();

		if (cost[current] < dist) continue;
		for (int i = 0; i < vec[current].size(); i++)
		{
			// 배열은 0부터 시작기에 -1을 해줌
			int next = vec[current][i].second - 1;
			int nextDist = dist + vec[current][i].first;

			// 목표 노드로 가는 비용 + 현재 위치까지의 비용 < 
			// 현재까지 알려진 목표 노드로의 비용
			if (nextDist < cost[next])
			{
				cost[next] = nextDist;
				pq.push(make_pair(-nextDist, next));
			}
		}
	}

} // E*logE + E

 

짧은 코드 설명

"현재 노드와 연결된 모든 간선"에 대해서 비용을 비교하고

조건에 맞으면 비용을 새로 업데이트 & pq에 등록!(다음 노드로 가기 위해)

이렇게 계속 업데이트가 되면 "모든 정점으로의 최단 경로"가 구해짐

 

 

 

시간복잡도 설명

모든 간선에 대해서 탐색을 함 ( E )

조건에 맞는 간선은 pq에 넣음 ( logE )

한번만 넣고 끝나는게 아니라 최대 'E'만큼 넣어지게 되기 때문에 ( E * logE )가 됨

 

즉 pq에서 정렬하는데만 (E * logE)가 되는거고 

모든 간선을 탐색하는 시간까지 더해서 ( E * log E + E )가 되는데

빅오 표기법에 의해 +E를 버리고 ( E * logE )가 됨