What is the difference between Dijkstra's and Bellman-Ford algorithm?

Dijkstra's algorithm is used to find the shortest path from a single source vertex to all other vertices in a graph with non-negative edge weights. Bellman-Ford can handle negative edge weights and can detect negative cycles.

When would you use A* search algorithm?

A* search is an extension of Dijkstra's algorithm that uses a heuristic to guide its search. It's commonly used in pathfinding and graph traversal to find the shortest path more efficiently.

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.