Dijkstra

Dijkstra's algorithm is a popular algorithm in computer science used to find the shortest path between nodes in a graph, particularly in weighted graphs where each edge has a numerical weight.

It was conceived by Dutch computer scientist Edsger W. Dijkstra in 1956.

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

1. Initialization: Assign a tentative distance value to every node. Set the initial node's distance to 0 and all others to infinity. Keep track of a priority queue (usually implemented with a min-heap) of all nodes, prioritized by their tentative distance values.

2. Visit Nodes: Visit each node in the graph starting from the initial node. For the current node, consider all of its neighbors and calculate their tentative distances through the current node. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one.

3. Update Priority Queue: After updating the tentative distances of neighboring nodes, reorder the priority queue based on the new tentative distances.

4. Repeat: Repeat steps 2 and 3 until all nodes have been visited.

5. Result: Once all nodes have been visited, the algorithm will have found the shortest path from the initial node to all other nodes.

pseudocode:

function Dijkstra(graph, start):
    create a priority queue Q
    for each vertex v in graph:
        if v is start:
            set distance[v] = 0
        else:
            set distance[v] = infinity
        add v to Q

    while Q is not empty:
        u = vertex in Q with minimum distance[u]
        remove u from Q
        for each neighbor v of u:
            alt = distance[u] + weight(u, v)
            if alt < distance[v]:
                distance[v] = alt
                previous[v] = u
    
    return distance[], previous[]

function dijkstra(graph, start) {
    let distances = {};
    let visited = {};
    let queue = new PriorityQueue();

    // Initialize distances
    for (let vertex in graph) {
        distances[vertex] = Infinity;
    }
    distances[start] = 0;

    // Enqueue the start node with priority 0
    queue.enqueue(start, 0);

    while (!queue.isEmpty()) {
        let currentVertex = queue.dequeue().element;

        if (!visited[currentVertex]) {
            visited[currentVertex] = true;

            for (let neighbor in graph[currentVertex]) {
                let distance = distances[currentVertex] + graph[currentVertex][neighbor];
                if (distance < distances[neighbor]) {
                    distances[neighbor] = distance;
                    queue.enqueue(neighbor, distance);
                }
            }
        }
    }
    return distances;
}

// Example graph
const graph = {
    A: { B: 4, C: 2 },
    B: { A: 4, D: 5 },
    C: { A: 2, D: 1 },
    D: { B: 5, C: 1 }
};

// Example usage
console.log(dijkstra(graph, 'A')); // Output: { A: 0, B: 3, C: 2, D: 3 }

In this example, graph represents an adjacency list where each key represents a vertex, and the value associated with each key is another object representing the neighbors of that vertex and the weight of the edge to each neighbor.

The function dijkstra calculates the shortest path from the start vertex to every other vertex in the graph and returns an object with the shortest distances.

The PriorityQueue is used to efficiently select the next vertex to visit based on its tentative distance.