# Shortest Path Algorithms

The shortest path problem is about finding a path between **2** vertices in a graph such that the total sum of the edges weights is minimum.

## Bellman Ford's Algorithm

Bellman Ford's algorithm is used to find the shortest paths from the source vertex to all other vertices in a weighted graph.

Shortest path contains at most **`n - 1`** edges, because the shortest path couldn't have a cycle.

> A very important application of Bellman Ford is to check if there is a negative cycle in the graph.

**Algorithm Steps:**

* The outer loop traverses from **0** : **n − 1**.
* Loop over all edges, check if the next node distance > current node distance + edge weight, in this case update the next node distance to "current node distance + edge weight".

| Time Complexity: `O(V  E)` |
| :------------------------: |

## Dijkstra's Algorithm

Dijkstra's algorithm has many variants but the most common one is to find the shortest paths from the source vertex to all other vertices in the graph.

**Algorithm Steps:**

* Set all vertices distances = infinity except for the source vertex, set the source distance = 0.
* Push the source vertex in a min-priority queue in the form (distance , vertex), as the comparison in the min-priority queue will be according to vertices distances.
* Pop the vertex with the minimum distance from the priority queue (at first the popped vertex = source).
* Update the distances of the connected vertices to the popped vertex in case of "current vertex distance + edge weight < next vertex distance", then push the vertex\
  with the new distance to the priority queue.
* If the popped vertex is visited before, just continue without using it.
* Apply the same algorithm again until the priority queue is empty.

| <p>Time Complexity: <code>O(V^2)</code></p><p><code>O(V + E log V)</code> with min-priority queue</p> |
| :---------------------------------------------------------------------------------------------------: |

On every iteration of the algorithm, a vertex is added with the minimum distance from the source and one that does not exist in the current shortest path.

## Floyd-Warshall's Algorithm

Floyd-Warshall's Algorithm is used to find the shortest paths between between all pairs of vertices in a graph, where each edge in the graph has a weight which is positive or negative.&#x20;

**The Algorithm Steps:**

For a graph with ***N*** vertices:

* Initialize the shortest paths between any **2** vertices with Infinity.
* Find all pair shortest paths that use **0** intermediate vertices, then find the shortest paths that use **1** intermediate vertex and so on.. until using all ***N*** vertices as intermediate nodes.
* Minimize the shortest paths between any **2** pairs in the previous operation.
* For any **2** vertices ***`(i,j)`*** , one should actually minimize the distances between this pair using the first ***K*** nodes, so the shortest path will be: ***`min(dist[i][k]+dist[k][j],dist[i][j])`***.

{% hint style="info" %}
***`dist[i][k]`*** represents the shortest path that only uses the first ***K*** vertices ***`i, k`***, \
\&#xNAN;***`dist[k][j]`*** represents the shortest path between the pair ***`k, j`***. \
As the shortest path will be a concatenation of the shortest path from to ***`i`*** to ***`k`***, then from ***`k`*** to ***`j`***.
{% endhint %}

| Time Complexity: **`O(V^3)`** |
| :---------------------------: |