Dijkstra's algorithm shortest path #dijkstra #graphs #algorithm

Dijkstra's algorithm 👇

Dijkstra's algorithm finds a single source shortest path (SSSP) on a weighted graph.
It can be used to find the shortest path to a particular node or the shortest paths to all graph's nodes.

The implementation of the algorithm is similar to the breadth-first search.
In the beginning, the distance to all the nodes is set to infinity (except the starting node, which has a distance of 0). The starting vertex is added to the queue together with the corresponding distance.

While items are in the queue, the algorithm is popping the nodes with the lowest distances.
If a node wasn't visited before, the algorithm checks the distance to adjacent nodes. If it's lower than the distance seen before, the distance is updated, and the node is added to the queue together with the corresponding distance.

Instead of a regular queue, Dijkstra's algorithm utilizes a priority queue, which sorts available destinations by distance and returns the one with the lowest value. Once the vertex is visited, it is guaranteed that the distance is minimal.

Pros:
Dijkstra's algorithm has a lower time complexity than the Bellman-Ford algorithm.

Cons:
It doesn't work on graphs with negative weights.

For connected graphs, the time complexity is equal to O(E*Log(V)), and the memory complexity is equal to O(E)* (if implemented with binary heap).

Best,
Albert 🤘

*Where V represents the number of vertices, and E the number of edges in the graph.

#dijkstra #dijkstras #shortestpath #graph #graphs #algorithm #coding #programming #computerscience #python #python3