CS 310 Graph Algorithms, Page 1'&$%Shortest Path ProblemTask: given a graph G, find the shortest path from a vertex u to avertex v.• If all edges are of the same length, then BFS will do.• But some times edges are not equal.☞ We associate a non-negative integer, called weight, witheach edge.☞ The weight of a path is the sum of the weights of all edgesin the path.☞ We want to find a minimum-weight path from u to v.CS 310 Graph Algorithms, Page 2'&$%Let G = (V, E) be a graph where V comprises a set of citiesinterconnected by a set of roads (edges) in E.• If the weight of a road (u, v) represents the distance from u tov, then a minimum weight x-y path is the shortest way to getto y from x.• If the weight of a road (u, v) represents the fee for using theroad (u, v), then a minimum weight x-y path is the cheapestway to get to y from x.CS 310 Graph Algorithms, Page 3'&$%Dijkstra’s Shortest Path Algorithm• Actually, it is a one-to-all shortest paths algorithm — given astarting vertex u, the algorithm finds the shortest paths from uto all the other nodes that are reachable from u.• Surprisingly, the one-to-one shortest path problem is no easierthan the one-to-all problem, meaning that Dijkstra’s algorithmis probably among the best we could find.• Dijkstra’s algorithm is specified by many important networkingstandards for the computation of paths to deliver computercommunication messages.☞ in the Internet, the OSPF protocol.CS 310 Graph Algorithms, Page 4'&$%Example0152342961581373CS 310 Graph Algorithms, Page 5'&$%Algorithm1. Initialize a dist array such that dist[start] = 0 and dist[i] = ∞for any vertex i other than start.2. Initialize a boolean array, marked, such that marked[i] = false,for every vertex i.3. Repeat the following steps until all vertices are marked.(a) Let u be the vertex, among the unmarked, with the smallestdistance; mark u.(b) For all neighbors v of u,dist[v] = min{dist[v], dist[u] + weight(u, v)}Complexity: O(N2), where N is the number of vertices in thegraph.CS 310 Graph Algorithms, Page 6'&$%Implementation Notes• How to find the smallest, unmarked vertex ?☞ sequential search in the dist array☞ heap (modified Dijkstra’s algorithm)• But the algorithm produces only the shortest distances, notshortest paths !CS 310 Graph Algorithms, Page 7'&$%The Predecessors Array01523429615813730 1 2 3 4 5PredWhenever dist[v] is set to dist[u] + weight(u, v), P red[v] is set to u.CS 310 Graph Algorithms, Page 8'&$%A Second Example01234 5 638574821560 1 2 3 4 5Pred60 1 2 3 4 5 6DistCS 310 Graph Algorithms, Page 9'&$%Minimum Spanning Tree ProblemLet G = (V, E) be a graph where V is a set of cities and E a set ofplanned, but not yet constructed, roads to connect cities in V .Let the weight of a road/edge be the cost to construct the road.Problem: using minimum cost, construct a set of roads to connectall the cities.01234 5 63857482156CS 310 Graph Algorithms, Page 10'&$%• For the minimum spanning tree problem, we focus onundirected graphs.• An undirected graph with N vertices is a tree if it is connectedand contains N − 1 edges.CS 310 Graph Algorithms, Page 11'&$%• A spanning tree of a graph G = (V, E) is a graph T = (V, E0)such that E0⊆ E and T is a tree.☞ In English, a spanning tree of a graph G uses as less edgesas possible to connect all the vertices in G.• Aminimum spanning tree of a weighted graph G is aspanning tree whose total weight is minimum among allspanning trees of G.01523429615813730152342961581373Total cost = 27 Total cost = 15CS 310 Graph Algorithms, Page 12'&$%Prim’s Algorithm1. Initialize a cost array such that cost[0] = 0 and cost[i] = ∞ forany vertex i other than 0.2. Initialize a pred array such that pred[0] = −1.3. Repeat the following steps until all vertices are marked.(a) Let u be the vertex, among the unmarked, with the smallestcost; mark u.(b) For each neighbor v of u,cost[v] = min{cost[v], weight(u, v)}(c) If cost[v] is set to weight(u, v) in the previous step, thenpred[v] = u.CS 310 Graph Algorithms, Page 13'&$%ExamplePred0 1 2 3 4 5 60 1 2 3 4 5 6Cost01234 5 63857482156CS 310 Graph Algorithms, Page 14'&$%Representing Weighted Graphs• In the adjacency table representation, edges[u][v] = −1indicates no edge from u to v, and edges[u][v] = w ≥ 0indicates an u to v edge with weight w.• In the adjacency list representation, add a weight field to eachlist node.CS 310 Graph Algorithms, Page 15'&$%01523429615813730 1 2 3 4 50123452 9615817 33neighborweightnext1 52 95 6 3 15 2 83 13 3 2 74 3012345CS 310 Graph Algorithms, Page 16'&$%Directed Acyclic Graph (DAG)A DAG is a directed graph containing no cycles.ADBECV = {A,B,C,D,E}E = {(A,C),(A,D),(A,E) (B,E),(C,B),(C,D), (E,D)}CS 310 Graph Algorithms, Page 17'&$%ExamplesConsider the graphs G1, G2, G3, and G4.Are they DAGs ?• G1:• G2:• G3:• G4:CS 310 Graph Algorithms, Page 18'&$%Topological Order on DAGSSuppose we have 10 tasks and a DAG where Ti→ Tjmeans thattask Timust be complete before task Tjcan start.23415678910Problem: find an ordering of tasks, calledtopological order, thatsatisfies the restricions presented by the DAG.Some possibilities:1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 101 → 3 → 4 → 6 → 2 → 5 → 7 → 9 → 8 → 101 → 4 → 3 → 2 → 6 → 5 → 9 → 8 → 7 → 10CS 310 Graph Algorithms, Page 19'&$%Topological Sort1. ∀ vertices v, compute predv, the number of tasks that vertexdepends on (directly).2. Find a vertex w where predw= 0. Output w.3. ∀ vertices x where w → x, decrement predx4. repeat steps 2 and 3 until no more vertices left in the graph.CS 310 Graph Algorithms, Page