Dijkstra's algorithm in JavaScript
Astik Sarathe
215
Graph TheoryCareerTypeScriptDijkstra's AlgorithmJavaScript

Dijkstra's algorithm is a graph search algorithm that is used to find the shortest path between two nodes (or vertices) in a graph.

Here is an outline of the algorithm:

  1. Initialize a priority queue of vertices, where the priority of a vertex is the shortest distance of that vertex from the source vertex.
  2. Initialize the distance to all other vertices to infinity, except for the distance to the source vertex, which is set to 0.
  3. Add the source vertex to the priority queue.
  4. Repeat the following until the priority queue is empty:
    1. Remove the vertex with the smallest distance from the priority queue.
    2. For each neighbor of the vertex, if the distance to the neighbor is greater than thedistance to the vertex plus the weight of the edge connecting them, update the distance to the neighbor and add the updated vertex to the priority queue.
  5. Return the array of distances.

Time and Space Complexity:

The time complexity of Dijkstra's algorithm is O(E log V), where E is the number of edges and V is the number of vertices in the graph. This is because the algorithm maintains a priority queue of vertices, and each vertex is added to and removed from the queue once. The operations of adding and removing elements from the queue have a time complexity of O(log V). Therefore, the overall time complexity is O(E log V).

The space complexity of Dijkstra's algorithm is O(V), where V is the number of vertices in the graph. This is because the algorithm stores the distances from the source vertex to all other vertices in an array.

Code

const { MinPriorityQueue } = require("datastructures-js");

/**
 * Finds the shortest paths from the source vertex to all other vertices in the graph,
 * using Dijkstra's algorithm.
 * 
 * @param {number} numVertices - The number of vertices in the graph.
 * @param {Array} edges - An array of arrays representing the edges of the graph. Each inner array
 *                        has three elements: the source vertex, the destination vertex, and the weight
 *                        of the edge.
 * @param {number} source - The source vertex, from which the shortest paths will be computed.
 * @return {Array} An array containing the shortest distances from the source vertex to all other
 *                 vertices in the graph.
 */
const dijkstra = (numVertices, edges, source) => {
        const adjacencyList = new Array(numVertices);
        for (let i = 0; i < numVertices; i++) {
                adjacencyList[i] = [];
        }

        // Populate the adjacency list
        for (const edge of edges) {
                adjacencyList[edge[0]].push([edge[1], edge[2]]);
        }

        // Initialize the distances to all other vertices to infinity, except for the source vertex
        const distances = new Array(numVertices).fill(Number.MAX_SAFE_INTEGER);
        distances[source] = 0;

        // Create the priority queue
        const priorityQueue = new MinPriorityQueue((arr) => arr[0]);

        // Add the source vertex to the priority queue
        priorityQueue.enqueue([0, source]);

        // Repeat the following until the priority queue is empty:
        while (!priorityQueue.isEmpty()) {
                // Remove the vertex with the smallest distance from the priority queue
                const pair = priorityQueue.dequeue();
                const distance = pair[0];
                const vertex = pair[1];

                // Update the distances of the neighbors of the vertex
                for (const neighbor of adjacencyList[vertex]) {
                        const neighborVertex = neighbor[0];
                        const edgeWeight = neighbor[1];
                        if (distances[neighborVertex] > edgeWeight + distance) {
                                distances[neighborVertex] = edgeWeight + distance;
                                // Add the updated vertex to the priority queue
                                priorityQueue.enqueue([edgeWeight + distance, neighborVertex]);
                        }
                }
        }

        return distances;
};

Let me know if you have any questions!
Please Upvote

bellman-ford-algorithm
https://leetcode.com/discuss/general-discussion/3013677/bellman-ford-algorithm-in-javascript(http://)

Comments (0)