Dijkstra's Algorithm

Question 1

What is Dijkstra’s algorithm?

Answer 1

it is an algorithm used to find the shortest path between a node and all other nodes in a graph

Question 2

What is the space complexity of Dijkstra’s algorithm?

Answer 2

O(V^2) when using an adjacency matrix
O(V + E) when using an adjacency list

Where V is the number of vertices

Question 3

What is the limitation of Dijkstra’s algorithm?

Answer 3

It assumes that the edges in the graph have nonnegative weights, if edges have negative weights Djiktra’s algorithm might pre-maturely determine the wrong shortest path, concluding that a longer path is shorter due to a negative weight. For graphs with negative edge weights, the suitable algorithm to use will be the Bellman-Ford algorithm

Question 4

What is the time complexity of Djiktra’s algorithm?

Answer 4

O(V^2) when using an adjacency matrix
O(V + E) when using an adjacency list