Graphs: Shortest path and mst Shortest Path: Single-source shortest path: Finding the shortest path from a particular vertex to all other vertices on a graph Think of taking a plane from Philadelphia International Airport to any other airport what is the shortest path? Note that this can be easily modified to find the shortest path from a single source to any other single source Other uses for shortest path: Maps: finding the shortest route, finding the fastest route

Vertices: intersections, Edges: roads (cost: distance, speed, or something else) Networks: for routing packets (data) across a network or the internet Vertices: routers Edges: connections (cost: time for travel) Epidemiology: modeling the spread of infectious diseases Vertices: individuals with disease Edges: contacts (cost: maybe likelihood of infection?) Assumptions:

Costs are positive numbers or zero Otherwise could find that the path with the lowest cost is infinite Not all vertices may be reachable from the single source Weights are not necessarily distance could be time, cost, likelihood, etc. Shortest paths may not be unique Dijkstra "Computer Science is no more about computers than astronomy is about telescopes." Dijkstra's algorithm Dijkstra's algorithm solves single-source shortest path problem Works on both directed and undirected graphs. all edges must have nonnegative weights.

Directed graph: Undirected Graph: Dijkstra Approach: Greedy (means make a locally optimal choice in the hope that the ultimate result will be optimal) Input: Weighted graph G={E,V} <- Graph is a set of edges and vertices source vertex vV, all edge weights are nonnegative Output: Lengths of shortest paths (or the shortest paths themselves) from a given source vertex vV to all other vertices Idea: Weve got a graph with edges and distances between connected edges (may be represented as a 2-dimensional array) Initiate all distances to infinity (or a really big number) except the distance from our starting vertex (0)

All vertexes go into a priority queue the unvisited vertex with the shortest distance, gets added to a set of visited nodes. Remove it from the queue. Recalculate all distances from initial vertex to all other vertices not visited yet Vertex with shortest distance from initial v is at top of queue take the minimum of the distance from the initial vertex v0 to vx or the distance from ther original vertex to the current vertex + the distance from the current vertex to vx Continue until all vertices have been visited (or no more vertices can be visited)

Dijkstra Animated Example Initiate all distances to infinity (or a really big number) except the distance from our starting vertex (0) V D[v] Pred[v] Visited A 0 null False B Inf null False C Inf null False

D Inf null False E Inf null False Dijkstra Example Update distances with the distances to vertices that can be reached from A V D[v] Pred[v] Visited A 0 null True B 10

A False C 3 A False D Inf null False E Inf null False Dijkstra Example V D[v] Pred[v] Visited A 0 null True

B 7 10 C A False C 3 A True D 11 Inf C null False E 5 Inf C null False Dijkstra Example Recalculate all distances from initial vertex to all other vertices not visited

yet Take the minimum of the distance from the initial vertex v0 to vx or the distance from ther original vertex to the current vertex + the distance from the current vertex to vx V V D[v] D[v] Pred[v] Pred[v] Visited A A 0 0 null null True B B 7 7 C

C False C C 3 3 A A True D D 11 11 C C False E E 5 5 C C False True Dijkstra Example

Take the next smallest path and add it to the visited set V D[v] Pred[v] Visited A 0 null True B 7 C False C 3 A True D 11 C False E

5 C True Dijkstra Example Recalculate distances based on smallest of either old distance or distance to added vertex plus distance from added vertex to unvisited node (in this case, no change) V D[v] Pred[v] Visited A 0 null True B 7 C False C 3

A True D 11 C False E 5 C True Dijkstra Example Take the next smallest path and add it to the visited set V D[v] Pred[v] Visited A 0 null True B 7

C True C 3 A True D 11 C False E 5 C True Dijkstra Example Recalculate distances based on smallest of either old distance or distance to added vertex plus distance from added vertex to unvisited node (D changes and prev node of D changes) V D[v]

Pred[v] Visited A 0 null True B 7 C True C 3 A True D 9 B False E 5 C True Dijkstra Example

V D[v] Pred[v] Visited A 0 null True B 7 C True C 3 A True D 9 B True E 5 C

True Find Shortest path from A to any node: Work Backwards: A-> D? Ds prev was B, Bs prev was C, Cs prev was A, so A->C->B->D A->E? Es prev was C, ss prev was A, so A->C->E V D[v] Pred[v] Visited A 0 null True B 7 C True C 3 A

True D 9 B True E 5 C True Represent a graph as a matrix A B C D E A 0 10 3 Inf

inf B inf 0 1 2 inf C inf 4 0 8 2 D inf

inf inf 0 7 E Inf inf inf 9 0 Pseudocode: function Dijkstra(Graph, source): for each vertex v in Graph{ // Initializations dist[v] = infinity ; // Unknown distance function from source to v previous[v] = undefined ; // Previous node in optimal path (maybe -1 to start) from source }//for dist[source] = 0 ;

// Distance from source to source Q = the set of all nodes in Graph ; // All nodes in the graph are put in a priority queue (many have a //cost of infinity right now (or largest int) while (Q is not empty) { // The main loop u = vertex in Q with smallest distance in dist[] ; // Start node in first case remove u from Q ; if (dist[u] == infinity) { break; // all remaining vertices are inaccessible from source } //if for each neighbor v of u in Q { // where v has not yet been removed from Q. alt = dist[u] + dist_between(u, v) ; if (alt < dist[v]) { dist[v] = alt ; // new shortest path to v previous[v] = u ; // shortest path goes through u decrease-key v in Q; // Reorder v in the priority queue } // if } //for } // while return dist;