[Algorithm] Dijkstra

 

When to use?

• 임의의 한 정점에서 모든 정점으로의 최단 경로 및 비용을 구할 때.
• 특정 출발 지점에서 도착지점까지의 최단 경로 및 비용을 구할 때

# shortest path # greedy

 

Algorithm

1. Create shortestPath Set, distance array table || (visited array)

2. initialize all vertices with make start node weight '0', reamin node weight 'INF'

3. set || priorityQueue != empty

   (a) Pick minimum vertex 

   (b) check all adjacent edge weight

     compare distance [adjacentVertex] vs distance[minimumVertex] + adjacentVertex weight

      => '<' update , >= nothing to do

   (c) set.insert || priorityQueue.insert()

 

⚠️Regardless of kind of graph (either undirected or directed). you need checking exsistence of target vertex in set using find function 
∵ There is possibility abscence of vertex (already poped from set or priority queue) 

// if already meet visited node-> ignore it since this is undirected graph
if (distanceSet.find(Node{adjacentVertex[DESTINATION_NODE], nodes[adjacentVertex[DESTINATION_NODE]].weight}) == distanceSet.end()) continue;

There is possibility that multiple access to node '7'  (3 times above graph.) ->in set or priority queue or visited boolean array

 

🖊️ use STL Set || Priority Queue for choosing minimum vertex.

 

Time Complexity

adjacent matrix -> O (V^2)

adjacent list + Priority Queue || Set -> O(E Log V)

 

 

 

Implement Dijkstra using Set

header

cpp

main

---

Reference

Dijkstra’s shortest path algorithm using set in STL - GeeksforGeeks

 

Dijkstra's Shortest Path Algorithm using priority_queue of STL - GeeksforGeeks