Algorithm

Dijkstra's algorithm, named after computer scientist Edsger Dijkstra, is a graph search algorithm that finds the shortest path between two nodes in a weighted graph. The algorithm works for graphs with non-negative edge weights and is commonly used in various applications, such as network routing protocols and maps.

Here's a basic overview of how Dijkstra's algorithm works:

  1. Initialization:

    • Assign a tentative distance value to every node. The initial node has a distance of 0, and all other nodes are assigned a distance of infinity.
    • Set the initial node as the current node.

  2. Visit Neighbors:

    • For the current node, consider all of its neighbors (nodes that can be reached directly from the current node).
    • Calculate the tentative distance from the initial node to each neighbor through the current node.
    • If the calculated distance is less than the previously assigned distance, update the distance.

  3. Mark as Visited:

    • After considering all neighbors of the current node, mark the current node as visited.
    • A visited node will not be checked again.

  4. Select Next Node:

    • Choose the unvisited node with the smallest tentative distance as the next "current node" and go back to step 2.

  5. Repeat:

    • Repeat steps 2-4 until the destination node is marked as visited or all reachable nodes have been considered.

  6. Path Reconstruction:

    • Once the destination node is marked as visited, the shortest path from the initial node to the destination node can be reconstructed by backtracking from the destination to the initial node, following the path of smallest tentative distances.

Dijkstra's algorithm guarantees the shortest path if all edge weights are non-negative. However, it may not work correctly if there are negative edge weights. For graphs with negative weights, algorithms like the Bellman-Ford algorithm are more appropriate.

Dijkstra's algorithm has a time complexity of O(V^2) for an adjacency matrix representation and O((V + E) * log(V)) using a priority queue with an adjacency list representation, where V is the number of vertices and E is the number of edges.

 

Code Examples

#1 Dijkstra's implement in Python

Code - Python Programming

import heapq

def dijkstra(graph, start):
    # Initialize distances with infinity for all nodes except the start node
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    
    # Use a priority queue to keep track of the nodes with the smallest tentative distance
    priority_queue = [(0, start)]
    
    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)
        
        # Skip if the current distance is greater than the known distance
        if current_distance > distances[current_node]:
            continue
        
        # Update distances for neighboring nodes
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            
            # If a shorter path is found, update the distance and add to the priority queue
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances

# Example usage
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

start_node = 'A'
result = dijkstra(graph, start_node)
print(f"Shortest distances from node {start_node}: {result}")
Copy The Code & Try With Live Editor

#2 Dijkstra's implement in Java

Code - Java Programming

import java.util.*;

class Graph {
    private int V;
    private List < List(V);
        for (int i = 0; i  <  V; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int source, int destination, int weight) {
        Node node = new Node(destination, weight);
        adjList.get(source).add(node);
    }

    public void dijkstra(int startVertex) {
        PriorityQueue < Node> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(node -> node.weight));
        int[] distance = new int[V];
        Arrays.fill(distance, Integer.MAX_VALUE);

        priorityQueue.add(new Node(startVertex, 0));
        distance[startVertex] = 0;

        while (!priorityQueue.isEmpty()) {
            int currentVertex = priorityQueue.poll().vertex;

            for (Node neighbor : adjList.get(currentVertex)) {
                int newDistance = distance[currentVertex] + neighbor.weight;

                if (newDistance  <  distance[neighbor.vertex]) {
                    distance[neighbor.vertex] = newDistance;
                    priorityQueue.add(new Node(neighbor.vertex, newDistance));
                }
            }
        }

        // Print the shortest distances
        System.out.println("Shortest distances from vertex " + startVertex + ":");
        for (int i = 0; i  <  V; i++) {
            System.out.println("To vertex " + i + ": " + distance[i]);
        }
    }

    private static class Node {
        int vertex;
        int weight;

        public Node(int vertex, int weight) {
            this.vertex = vertex;
            this.weight = weight;
        }
    }
}

public class DijkstraExample {
    public static void main(String[] args) {
        int V = 5;
        Graph graph = new Graph(V);

        graph.addEdge(0, 1, 2);
        graph.addEdge(0, 3, 1);
        graph.addEdge(1, 2, 3);
        graph.addEdge(1, 3, 2);
        graph.addEdge(2, 4, 1);
        graph.addEdge(3, 2, 5);
        graph.addEdge(3, 4, 4);

        int startVertex = 0;
        graph.dijkstra(startVertex);
    }
}
Copy The Code & Try With Live Editor

#3 Dijkstra's implement in C

Code - C Programming

#include <stdio.h>
#include <limits.h>

#define V 9 // Number of vertices in the graph

int minDistance(int dist[], int sptSet[]) {
    int min = INT_MAX, min_index;

    for (int v = 0; v  <  V; v++) {
        if (sptSet[v] == 0 && dist[v] <= min) {
            min = dist[v];
            min_index = v;
        }
    }

    return min_index;
}

void printSolution(int dist[]) {
    printf("Vertex \t Distance from Source\n");
    for (int i = 0; i  <  V; i++)
        printf("%d \t %d\n", i, dist[i]);
}

void dijkstra(int graph[V][V], int src) {
    int dist[V]; // The output array dist[i] holds the shortest distance from src to i
    int sptSet[V]; // sptSet[i] will be true if vertex i is included in the shortest path tree or the shortest distance from src to i is finalized

    // Initialize all distances as INFINITE and sptSet[] as false
    for (int i = 0; i  <  V; i++) {
        dist[i] = INT_MAX;
        sptSet[i] = 0;
    }

    // Distance of source vertex from itself is always 0
    dist[src] = 0;

    // Find shortest path for all vertices
    for (int count = 0; count  <  V - 1; count++) {
        // Pick the minimum distance vertex from the set of vertices not yet processed.
        int u = minDistance(dist, sptSet);

        // Mark the picked vertex as processed
        sptSet[u] = 1;

        // Update dist value of the adjacent vertices of the picked vertex.
        for (int v = 0; v  <  V; v++) {
            // Update dist[v] only if it is not in the sptSet, there is an edge from u to v, and the total weight of path from src to v through u is less than the current value of dist[v]
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    // Print the constructed distance array
    printSolution(dist);
}

int main() {
    // Example graph represented as an adjacency matrix
    int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
                       {4, 0, 8, 0, 0, 0, 0, 11, 0},
                       {0, 8, 0, 7, 0, 4, 0, 0, 2},
                       {0, 0, 7, 0, 9, 14, 0, 0, 0},
                       {0, 0, 0, 9, 0, 10, 0, 0, 0},
                       {0, 0, 4, 14, 10, 0, 2, 0, 0},
                       {0, 0, 0, 0, 0, 2, 0, 1, 6},
                       {8, 11, 0, 0, 0, 0, 1, 0, 7},
                       {0, 0, 2, 0, 0, 0, 6, 7, 0}};

    dijkstra(graph, 0);

    return 0;
}
Copy The Code & Try With Live Editor

#4 Dijkstra's implement in C++

Code - C++ Programming

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

// Define a structure to represent a graph edge
struct Edge {
    int destination;
    int weight;
};

// Define a structure to represent a graph node
struct Node {
    vector < Edge> edges;
};

// Dijkstra's algorithm function
void dijkstra(vector < Node>& graph, int start) {
    int n = graph.size();
    vector<int> distance(n, INT_MAX);
    vector < bool> visited(n, false);

    // Priority queue to get the minimum distance vertex efficiently
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater < pair<int, int>>> pq;

    distance[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if (visited[u]) {
            continue;
        }

        visited[u] = true;

        // Update the distance to adjacent nodes
        for (const Edge& edge : graph[u].edges) {
            int v = edge.destination;
            int w = edge.weight;

            if (!visited[v] && distance[u] != INT_MAX && distance[u] + w  <  distance[v]) {
                distance[v] = distance[u] + w;
                pq.push({distance[v], v});
            }
        }
    }

    // Output the shortest distances from the start node
    cout << "Shortest distances from node " << start << ":\n";
    for (int i = 0; i  <  n; ++i) {
        cout << "Node " << i << ": " << distance[i] << endl;
    }
}

int main() {
    // Example graph representation
    vector < Node> graph = {
        {{1, 4}, {2, 1}},
        {{3, 2}},
        {{1, 2}, {3, 5}},
        {}
    };

    // Start Dijkstra's algorithm from node 0
    dijkstra(graph, 0);

    return 0;
}
Copy The Code & Try With Live Editor
Advertisements

Demonstration

Dijkstra's Data Structure and Algorithm