Search⌘ K
Home
Courses
Mastering Algorithms for Problem Solving in Java

Introduction to Shortest Paths

Explore the fundamentals of shortest path problems in weighted directed graphs. Understand how to determine the shortest path from a source to a target vertex through shortest path trees, and learn about challenges and solutions involving negative edge weights and graph directionality.

We'll cover the following...

Weighted directed graph (two vertices)

Suppose we are given a weighted directed graph G=(V,E,w)G = (V, E, w) with two special vertices, and we want to find the shortest path from a source vertex ss to a target vertex tt. That is, we want to find the directed path PP starting at ss and ending at tt that minimizes the function

w(P):=∑u→vϵPw(u→v).w(P) := \underset{u\rightarrow v \epsilon P}{\sum} w(u\rightarrow v). ...