Dijkstra’s Algorithm for Finding Shortest Paths in a Graph

Posted on Aug 2, 2024 in Computers

Dijkstra’s Algorithm for Finding Shortest Paths in a Graph

Dijkstra’s algorithm is a greedy algorithm that solves the single-source shortest path problem on a weighted, directed graph. Given a graph with a source vertex, the algorithm finds the shortest path from the source vertex to every other vertex in the graph.

The Algorithm

1. Initialize a distance array d, where d[v] represents the current best known distance from the source vertex to vertex v. Initially, set d[v] to infinity for all vertices except the source vertex, which is set to 0.
2. Initialize a predecessor array p, where p[v] represents the predecessor of vertex v in the shortest path from the source vertex. Initially, set p[v] to -1 for all vertices.
3. Create a set S of visited vertices. Initially, S is empty.
4. While S does not contain all vertices in the graph:
   1. Find the vertex u in V – S with the smallest d[u].
   2. Add u to S.
   3. For each neighbor v of u:
      1. If d[u] + weight(u, v) < d[v], then update d[v] to d[u] + weight(u, v) and set p[v] to u.

Example

Consider the following weighted graph:

    A --3-- B
   / \     |
  2   \    | 1
   \   \   |/
    \   5--C
     \ /    |
      D --4-- E

If we apply Dijkstra’s algorithm to this graph with vertex A as the source, we get the following results:

| Vertex | Distance | Predecessor | |—|—|—| | A | 0 | – | | B | 3 | A | | C | 5 | B | | D | 7 | C | | E | 9 | D |

The shortest path from A to E is A -> B -> C -> D -> E, with a total weight of 9.

Implementation

import java.util.*;

public class Dijkstra {

    private static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        // Graph represented as an adjacency matrix
        int[][] graph = {
            {0, 3, 0, 0, 0},
            {3, 0, 1, 0, 0},
            {0, 1, 0, 5, 0},
            {0, 0, 5, 0, 4},
            {0, 0, 0, 4, 0}
        };

        // Source vertex
        int source = 0;

        // Initialize distances and predecessors
        int[] distances = new int[graph.length];
        int[] predecessors = new int[graph.length];
        for (int i = 0; i < graph.length; i++) {
            distances[i] = INF;
            predecessors[i] = -1;
        }
        distances[source] = 0;

        // Set of visited vertices
        Set<Integer> visited = new HashSet<>();

        // Main loop
        while (visited.size() < graph.length) {
            // Find the unvisited vertex with the smallest distance
            int minDistance = INF;
            int minVertex = -1;
            for (int i = 0; i < graph.length; i++) {
                if (!visited.contains(i) && distances[i] < minDistance) {
                    minDistance = distances[i];
                    minVertex = i;
                }
            }

            // Visit the vertex
            visited.add(minVertex);

            // Update distances and predecessors
            for (int i = 0; i < graph.length; i++) {
                if (graph[minVertex][i] > 0 && !visited.contains(i)) {
                    int newDistance = distances[minVertex] + graph[minVertex][i];
                    if (newDistance < distances[i]) {
                        distances[i] = newDistance;
                        predecessors[i] = minVertex;
                    }
                }
            }
        }

        // Print the shortest paths
        for (int i = 0; i < graph.length; i++) {
            System.out.println("Shortest path from " + source + " to " + i + ": " + distances[i]);
            if (predecessors[i] != -1) {
                System.out.print("Path: " + i);
                int current = predecessors[i];
                while (current != source) {
                    System.out.print(" <- " + current);
                    current = predecessors[current];
                }
                System.out.println(" <- " + source);
            }
        }
    }
}