Reference no: EM131381665

Problem: Suppose that you have a directed graph G = (V, E) with positive edge lengths `(e) for all edges e ∈ Eand positive vertex costs c(v) for all v ∈ V . Define the length of a path from a to b to be the sum ofall edge lengths `(e) for all edges e in the path plus the sum of all the vertex costs c(v) for all verticesv in the path (including a and b.) Define the distance from a to b to be the length of the path withthe shortest length. Note that the distance from a vertex a to itself has distance c(a).