Introduction to Shortest Paths
Explore the core concepts of shortest path algorithms in weighted directed graphs. Understand finding minimum-weight paths, shortest path trees, and challenges with negative edge weights. This lesson helps build a foundation for solving shortest path problems using algorithms like Dijkstra and Bellman-Ford.
Weighted directed graph (two vertices)
Suppose we are given a weighted directed graph with two special vertices, and we want to find the shortest path from a source vertex to a target vertex . That is, we want to find the directed path starting at and ending at that minimizes the function
...