Dijkstra's Algo

It is the greedy Algo to find the min/max-cost path of a graph.

The implementation is using

• BFS

• PriorityQueue: BFS use a queue to keep the node needing to iterate, Dikstra's Algo uses a priority queue to keep the next node is the min/max cost instead.

• Use an array to keep the min/max value in each node

Time complexity:

O(E*logV), where E is the total edges count, V is the vertex count

• We don't revisit the same node, which means we don't reuse the same edge.

• For each edge, we pop out the best node (according to our principle) from a min(max)Heap.

  • it takes log V,

• Total computation is E * log V