Dijkstras Algorithm (다익스트라 알고리즘)

• Function

Algorithm for finding the shortest paths between nodes in a graph

It fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in a graph

It uses a data structure for storing and querying partial solutions sorted by distance from the "source" node (Queue, prioirty - Queue in C++)

 

• Time Complexity

prioirty queue - $$ \Theta ((\left| V \right| + \left| E \right|)log\left| V \right|) $$ (V : number of nodes, E : number of edges)

array - $$ \Theta (\left| V \right|^2) $$

 

• Algorithm

Starting at initial node, distance of node Y = distance between initial node to node Y

1. Mark all nodes unvisited ( of Set All nodes distance to Max_Val, if distance of some node is Max_Val it is unvisited)

2. Set Initial node's distance 0

Start While iterate ---------

3. For the current node (At first, Source Node) Find all of its unvisited neighbors. Calculate their distance by Sum of current node distance and distance between current node and neighbor. Compare the newly distance to the currently assigned and assign it the smaller one. And Push to priority Queue

4. When we are done considering all of the unvisited neighbors of the current node, Mark the current node as visited. (Pop it from priority Queue)

5. If the destination node has been marked visited, Or size of Queue is Zero. Find Shortest Path (lowest distance) to Target Node

 

• Extra Information

- Queue

- Priority Queue

- Graph

- LeetCode : 743

 

• Example Code

class Solution {
public:
	vector<pairInt>Graph[MaxNodeSize];
	int ArrDistance[MaxNodeSize];

	void DijkstraAlgorithm(int SrcNode)
	{
		int CurrentNode;
		int i = 0;
		int DstNode = 0;
		int DelayTime = 0;

		priority_queue<pairInt, vector<pairInt>, greater<pairInt>> Queue;

		for (i = 0; i < MaxNodeSize; ++i) ArrDistance[i] = INT32_MAX;
		ArrDistance[SrcNode] = 0;
		Queue.push({ 0, SrcNode });

		while (!Queue.empty())
		{
			CurrentNode = Queue.top().second;
			Queue.pop();

			for (i = 0; i < Graph[CurrentNode].size(); ++i) // Search Neighbors
			{
				DstNode = Graph[CurrentNode][i].first;
				DelayTime = Graph[CurrentNode][i].second;

				if (ArrDistance[DstNode] > ArrDistance[CurrentNode] + DelayTime)
				{
					ArrDistance[DstNode] = ArrDistance[CurrentNode] + DelayTime;
					Queue.push({ ArrDistance[DstNode], DstNode });
				}
				else
				{
					// Do Nothing
				}
			}
		}
	}
    };

Reference : https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm