Graph Algorithms

Shortest Path Algorithms

Master shortest path algorithms like Dijkstra's and Bellman-Ford. This guide provides expert solutions, practice problems, and AI-powered hints to help you ace your coding interviews.

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest paths between nodes in a graph. It is a greedy algorithm that maintains a set of vertices whose shortest distance from the source is already known.

                            function dijkstra(graph, startNode) {
                              // graph should be an adjacency list with weights
                            const distances = {};
                            const pq = new PriorityQueue({ compare: (a, b) => a[1] - b[1] });
                            const previous = {};
                            
                            for (let vertex in graph) {
                            if (vertex === startNode) {
                            distances[vertex] = 0;
                            pq.enqueue([vertex, 0]);
                            } else {
                            distances[vertex] = Infinity;
                            }
                            previous[vertex] = null;
                            }
                            
                            while (!pq.isEmpty()) {
                            let [minNode] = pq.dequeue();
                            
                            for (let neighbor in graph[minNode]) {
                            let newDist = distances[minNode] + graph[minNode][neighbor];
                            if (newDist < distances[neighbor]) {
                            distances[neighbor] = newDist;
                            previous[neighbor] = minNode;
                            pq.enqueue([neighbor, newDist]);
                            }
                            }
                            }
                            
                            return { distances, previous };
                            }
                        

AI Coach Hint: Dijkstra's algorithm is a cornerstone of graph theory. Remember that it doesn't work with negative edge weights. For that, you'll need to use the Bellman-Ford algorithm. A priority queue is essential for an efficient implementation of Dijkstra's.