The Shortest Path Problem ● Let G=(,E)be a directed graph in which each edge has a nonnegative length,and a distinguished vertex s called the source.The single-source shortest path problem,or simply the shortest path problem,is to determine the distance from s to every other vertex in where the distance from vertex s to vertex xis defined as the length of a shortest path from sto x. For simplicity,we will assume that V1,2,...,n) and s=1. This problem can be solved using a greedy technique known as Dijkstra's algorithm.The Shortest Path Problem ◼ Let G=(V, E) be a directed graph in which each edge has a nonnegative length, and a distinguished vertex s called the source. The single-source shortest path problem, or simply the shortest path problem, is to determine the distance from s to every other vertex in V, where the distance from vertex s to vertex x is defined as the length of a shortest path from s to x. ◼ For simplicity, we will assume that V={1, 2, …, n} and s=1. ◼ This problem can be solved using a greedy technique known as Dijkstra’s algorithm