6. Dijkstra’s Algorithm #

Created Sunday 26 April 2020

Given a graph, directed or undirected with weights. Should not have NEGATIVE weights.

• Trick for negatives: Add the most negative value(+ve) to all the weights. Solve using dijkstra, then subtract each edge by the negative value.

• We find the shortest path from a start vertex to all of the other vertices.

• We have two lists: visited and unvisited vertices.

Algorithm:

1. Pick a vertex from the **unvisited **vertices with the least distance from the start. These may be non-neighbours.
2. Explore it, i.e update the distance value of a neighbour if distance(curr->neighbour) + distance(start->curr) < distance(start->neighbour). Also update it’s parent(or predecessor). Do this for all the unvisited neighbours. We have confidence in our **greedy algo. **Greedy Choice Property. (No reconsiderations)
3. After we have explored all the vertices, stop.
4. We can trace the path too.
5. Visual aid - A table with <visited, vertex, distance_from_start, parent> + is_visited_array.

https://www.topcoder.com/community/competitive-programming/tutorials/greedy-is-good/

Time Complexity is O(V^2^) - for adjacency matrix

• We can use an adjacency list, O(VE)
• We can use a priority queue for the minimum thing. O((V+E)*logV)