[C++] Dijkstra algorithm(다익스트라 알고리즘)

※ 무엇

음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘(최단 경로 문제, Shortest Path Problem)이다.

다익스트라 알고리즘은 방향성 비순환 그래프 ( DAG, Directed Acyclic Graph ) 또는 사이클을 가진 경우 가중치가 양수일 때에만 적용이 된다.

 

다익스트라가 고안한 알고리즘으로, 그가 처음 고안한 알고리즘은 O(V^2)의 시간복잡도를 가졌다. 이후 우선순위 큐, 피보나치 힙 등을 이용한 더욱 개선된 알고리즘이 나오며, O((V+E)logV) (V는 정점의 개수, E는 한 정점의 주변 노드)의 시간복잡도를 가지게 되었다.
O((V+E)logV)의 시간복잡도를 가지는 이유는 각 노드마다 미방문 노드 중 출발점으로부터 현재까지 계산된 최단 거리를 가지는 노드를 찾는데 O(VlogV)의 시간이 필요하고, 각 노드마다 이웃한 노드의 최단 거리를 갱신할 때 O(ElogV)의 시간이 필요하기 때문이다.

 

프림과 유사하게 보이는 이유는 트리를 유지하면서 노드에서 노드로 이동하며 계산하기 때문임.

기존 프림 방식에서 VlogV(최단거리가 되는 엣지 찾기) 가 추가되고, ElogV가 노드 마다 시작부터 최단거리를 갱신하는 거로 바뀌는거(프림은 해당 노드에서 다음 노드까지 거리 중 최단)

※ 코드

void Dijkstra(Node* startNode, Graph<T>*graph)
	{
		int* weights = new int[Count];//가중치
		Node** shorts = new Node*[Count];//
		Node** connected = new Node*[Count];//연결 노드 확인
		Node** parents = new Node*[Count];//어디 출신 이냐

		Edge* currentEdge = NULL;
		Node* currentNode = Head;//시작 노드
		for (int i = 0; currentNode != NULL; i++)//초기화
		{
			Node* newNode = CreateNode(currentNode->Data);
			graph->AddNode(newNode);

			weights[i] = INT_MAX;//초기화 안된놈 최댓값으로 설정해서 나중에 비교할 때 묵살하게
			shorts[i] = newNode;
			connected[i] = NULL;
			parents[i] = NULL;

			currentNode = currentNode->Next;//다음 노드
		}

		PQueue<Node*>queue(10);
		PQueue<Node*>::Node startQNode = PQueue<Node*>::Node(0, startNode);//시작 노드

		queue.Insert(startQNode);
		weights[startNode->index] = 0;//안움직였으니깐 가중치 0이죠
		while (queue.Empty() == false)
		{
			PQueue<Node*>::Node poped = queue.RemoveMin();
			currentNode = poped.Data;

			connected[currentNode->index] = currentNode;

			currentEdge = currentNode->Edge; 
			while (currentEdge != NULL)//노드에 연결된 모든 간선 넣자
			{
				Node* targetNode = currentEdge->Target;
				
                //미방문 노드 중 출발점으로부터 현재까지 계산된 최단 거리를 가지는 노드를 찾는데 
                //O(VlogV)의 시간이 필요 // 최악의 경우 모든 간선에 대해 비교(우선순위 큐로 처리된 간선들과) 하므로
                //VlogV 임. 이 말은 간선의 갯수가 작을 수록 최악의 상황에 가까워짐(생략되는게 적으니깐)
				bool b = true;
				b &= connected[targetNode->index] == NULL;
				b &= weights[currentNode->index] + currentEdge->Weight < weights[targetNode->index];

				if (b == true)
				{
					PQueue<Node*>::Node newNode = PQueue<Node*>::Node(currentEdge->Weight, targetNode);//
					queue.Insert(newNode);

					parents[targetNode->index] = currentEdge->Start;//해당 노드의 부모 교체
					weights[targetNode->index] = weights[currentNode->index] + currentEdge->Weight;//각 노드마다 이웃한 노드의 최단 거리를 갱신할 때 O(ElogV)의 시간이 필요 // VlogV 와 독립 사건임
				}//if(b

				currentEdge = currentEdge->Next;
				
			}//while(currentEdge
		}
		for (int i = 0; i < Count; i++)
		{
			if (parents[i] == NULL)//부모가 없는 시작 노드 무시
				continue;

			int start = parents[i]->index;
			int target = i;

			graph->AddEdge(shorts[start], Graph<T>::CreateEdge(shorts[start], shorts[target], weights[i]));//그래프에 간선 추가 (시작 노드, 간선 정보)

			cout << shorts[start]->Data << ","<<shorts[target]->Data<<"," << weights[i] << endl;
		}

		cout << endl;

		delete[] connected;
		delete[] parents;
		delete[] shorts;
		delete[] weights;
	}