Dijkstra's Algorithm

Dijkstra's Algorithm is a popular greedy algorithm used to find the shortest path from a starting vertex to all other vertices in a weighted graph. It is particularly useful for solving the single-source shortest path problem and is applied in various fields, including computer networking, transportation, and GPS navigation.

How Dijkstra's Algorithm Works

1. Initialization:

   • Create a set to keep track of vertices whose minimum distance from the source is calculated (initially empty).
   • Assign a tentative distance value to every vertex. Set the source vertex's distance to 0 and all others to infinity.

2. Vertex Selection:

   • Choose the vertex with the smallest tentative distance from the set of unvisited vertices. Initially, this is the source vertex.

3. Neighboring Vertices:

   • For the selected vertex, consider all of its neighbors.

4. Distance Update:

   • Calculate their tentative distances through the current vertex. Compare the newly calculated tentative distance to the current assigned value and update if smaller.

5. Mark as Visited:

   • Once we have considered all the neighbors of the current vertex, mark the current vertex as visited and remove it from the unvisited set.

6. Repeat:

   • Continue this process until all vertices are visited or if the smallest tentative distance from the unvisited set is infinity.

7. Completion:

   • The algorithm has calculated the shortest distance from the source vertex to all other vertices.

Key Features

• Optimality: Dijkstra's Algorithm guarantees the shortest path if edge weights are non-negative.

• Single-Source Shortest Path: It is used for finding the shortest path from a single source vertex to all other vertices in the graph.

Efficiency

• Time Complexity: Dijkstra's Algorithm has a time complexity of O(V^2) with a basic implementation. With a priority queue or min-heap, it can achieve a time complexity of O(E + V log V), where E is the number of edges and V is the number of vertices.

• Space Complexity: The space complexity depends on the data structures used. In the worst case, it can be O(E + V).

Applications

• Routing and Navigation: Dijkstra's Algorithm is used in GPS navigation and computer networking to find the shortest paths between locations.

• Transportation Planning: It helps plan efficient transportation routes for vehicles, including cars, buses, and delivery trucks.

• Robotics: Dijkstra's Algorithm is used in robotics for path planning and obstacle avoidance.

Limitations

• Non-Negative Weights: The algorithm works only for graphs with non-negative edge weights. Negative weights can lead to incorrect results, and for graphs with negative cycles, the algorithm doesn't work.

• Complexity with Priority Queue: While efficient with a priority queue, Dijkstra's Algorithm can be computationally expensive for large graphs.

• Doesn't Handle Negative Weights: For graphs with negative edge weights, other algorithms like Bellman-Ford are more suitable.

Dijkstra's Algorithm Implementation in JavaScript

Here's an example of Dijkstra's Algorithm implemented in JavaScript:

class Graph {
    constructor() {
        this.vertices = [];
        this.edges = {};
    }
 
    addVertex(vertex) {
        this.vertices.push(vertex);
        this.edges[vertex] = {};
    }
 
    addEdge(vertex1, vertex2, weight) {
        this.edges[vertex1][vertex2] = weight;
        this.edges[vertex2][vertex1] = weight;
    }
 
    dijkstra(source) {
        const distance = {};
        this.vertices.forEach((vertex) => (distance[vertex] = Infinity));
        distance[source] = 0;
 
        const unvisited = new Set(this.vertices);
        while (unvisited.size > 0) {
            const current = this.minDistanceVertex(unvisited, distance);
            unvisited.delete(current);
 
            for (const neighbor in this.edges[current]) {
                const newDistance = distance[current] + this.edges[current][neighbor];
                if (newDistance < distance[neighbor]) {
                    distance[neighbor] = newDistance;
                }
            }
        }
 
        return distance;
    }
 
    minDistanceVertex(vertices, distance) {
        let minDistance = Infinity;
        let minVertex;
        for (const vertex of vertices) {
            if (distance[vertex] < minDistance) {
                minDistance = distance[vertex];
                minVertex = vertex;
            }
        }
        return minVertex;
    }
}
 
// Example usage
const graph = new Graph();
const vertices = ["A", "B", "C", "D", "E"];
vertices.forEach((vertex) => graph.addVertex(vertex));
 
graph.addEdge("A", "B", 2);
graph.addEdge("A", "C", 4);
graph.addEdge("B", "C", 1);
graph.addEdge("B", "D", 7);
graph.addEdge("C", "D", 3);
graph.addEdge("C", "E", 5);
graph.addEdge("D", "E", 2);
 
const sourceVertex = "A";
const shortestDistances = graph.dijkstra(sourceVertex);
console.log(`Shortest distances from vertex ${sourceVertex}:`, shortestDistances);