Can you find the shortest path between two nodes in a graph?

One of the most common and effective methods for finding the shortest path in a graph is Dijkstra’s Algorithm.

Dijkstra’s Algorithm works by visiting vertices in the graph starting from the object’s starting point. It then repeatedly selects the unvisited vertex with the lowest distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor’s distance if smaller. Mark visited (set to red) when done with neighbors.

Here is a step by step breakdown of Dijkstra’s algorithm using pseudo code:

1. Create a set (sptSet) that will contain all the vertices included in the shortest path tree i.e., the shortest distance from the source vertex to the vertex has been finalized. 2. Initialize distance values as:

- Distance of source vertex from itself is always 0.
d[source] = 0

- Distance of all other vertices from the starting point is set to infinity initially.
d[v] = ∞       v ≠ source

3. Until sptSet includes all vertices, follow the subsequent steps:

- Pick any vertex ‘u‘ that isn’t contained within the sptSet and has a minimum distance-value index.

- Include ‘u‘ to the sptSet.

- Based on the current node, update distance values of all adjacent vertices of picked vertex ‘u‘. For every adjacent vertex ‘v‘, if the sum of distance value of ‘u‘ from source and the weight of edge ‘u-v‘ is less than the distance value of ‘v‘, then update the distance value of ‘v‘.

The formula to update the adjacent vertices is: if d[u] + cost_u, v < d[v] then update d[v] = d[u] + cost_u, v

Let’s take an example of the following graph:

             2     3
          A----B----E
         /|\   |     |\
        / | \  |     | \
       6  1  3 2     7  2
      /   |   \|     |   \
     /    |    \     |    \
    C-----D----F----G-----H
      1    2    1    2     1

The shortest path from vertex ‘A‘ to ‘H‘ is A->B->E->H with cost=2+3+2=7.

Dijkstra’s Algorithm has a time complexity of O(V²) (for adjacency matrix representation of a graph) where ‘V‘ is the number of vertices. However, using binary heap, time complexity can be reduced to ‘O(E log V)‘, where ‘E‘ is the number of edges.

You might want to use Dijkstra’s algorithm if, for example, you are building a software for a GPS, and you need to calculate the quickest route from one place to another.

However, It’s worth noting that Dijkstra’s Algorithm doesn’t work with graphs that contain negative weight edges. For graphs with negative weight edges, one can use Bellman–Ford algorithm.