| TOPIC: Dijkstra's Algorithm | |
| DEFINITION: Dijkstra's Algorithm is a method for finding the shortest path between two points in a weighted graph or network. It solves the single-source shortest paths problem, where the goal is to determine the minimum distance from a starting node to all other nodes in the graph. This algorithm is particularly useful when the graph contains non-negative edge weights. | |
| TIME_COMPLEXITY: The time complexity of Dijkstra's Algorithm is O(|E|log|V|) in the worst case, where |E| is the number of edges and |V| is the number of vertices, because it uses a priority queue to efficiently select the next node to visit. | |
| SPACE_COMPLEXITY: The space complexity is O(|V| + |E|), as the algorithm needs to store the distance to each node and the graph's adjacency list or matrix. | |
| USE_WHEN: Dijkstra's Algorithm is the right tool when you need to find the shortest path in a weighted graph with non-negative edge weights, such as in network routing or traffic optimization problems. It's particularly useful when the graph is sparse, meaning that most nodes are not directly connected. | |
| AVOID_WHEN: You should avoid using Dijkstra's Algorithm when the graph contains negative-weight edges, as it can lead to incorrect results; instead, use the Bellman-Ford Algorithm. Additionally, for unweighted graphs, a simpler algorithm like Breadth-First Search (BFS) may be more efficient. | |
| EXAMPLE: | |
| Start with a graph: | |
| A -> B (weight 2) | |
| A -> C (weight 4) | |
| B -> C (weight 1) | |
| B -> D (weight 5) | |
| C -> D (weight 3) | |
| Initialize distances: | |
| A: 0 | |
| B: infinity | |
| C: infinity | |
| D: infinity | |
| Visit A, update distances: | |
| A: 0 | |
| B: 2 | |
| C: 4 | |
| D: infinity | |
| Visit B, update distances: | |
| A: 0 | |
| B: 2 | |
| C: 3 | |
| D: 7 | |
| Visit C, update distances: | |
| A: 0 | |
| B: 2 | |
| C: 3 | |
| D: 6 | |
| Visit D, no updates needed | |
| Result: shortest path from A to D is A -> B -> C -> D with distance 6 | |
| REAL_WORLD_ANALOGY: Dijkstra's Algorithm is like planning a road trip, where you want to find the shortest route between two cities on a map with varying road lengths and traffic conditions. | |
| SOURCE_NOTE: Concepts referenced from general knowledge of graph algorithms and data structures. |