Graphs: Shortest path and mst Shortest Path: Single-source

Graphs: Shortest path and mst Shortest Path: Single-source

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;

Recently Viewed Presentations

  • Starter Can you think of an opposite word/phrase

    Starter Can you think of an opposite word/phrase

    'Kamikaze' by Beatrice Garland. Suicide attacks were made by Japanese kamikaze pilots in World War II. They would fly bombs into ships and it was considered an honour to die for your country. Kamikaze. All can understand the poem and...
  • The Magpie and the Chameleon

    The Magpie and the Chameleon

    The Magpie and the Chameleon
  • The Physics of Leaf Wetness - wamis.org

    The Physics of Leaf Wetness - wamis.org

    A few automated agro meteorological stations are placed in the area The region is covered by a weather radar The problem of estimating leaf wetness duration is closely connected to plant pathology The system for making measurements There are a...
  • Biological Affinity-Based Methods of DNA Methylation Detecton ...

    Biological Affinity-Based Methods of DNA Methylation Detecton ...

    Biological Affinity-Based Methods of DNA MethylationDetecton: Genome Wide The Basic Idea Some antibodies have a high affinity for methylated DNA, or methylation-specific proteins, which means that they will bind to methylated sites on DNA, but not to non-methylated sites
  • A plague on both your houses What is

    A plague on both your houses What is

    A way with words. Shakespeare added ... Themes, Symbols. and . ... There are many near-misses and points where things could have so easily gone another way and ended happily, but didn't, that it seems like their fate or destiny...
  • The Seven Habits of Highly Effective People

    The Seven Habits of Highly Effective People

    Put First Things First Based on the work of Stephen Covey I spend my time on things that are most important. This means I say no to things I should not do. I set priorities, make a schedule, and follow...
  • Vacation scholarship presentation

    Vacation scholarship presentation

    Data analysis. Performed through the excessive use of SPSS and excessive consumption of time !!!!! Penny Robinson the Biostatistician in the Women's Health Dept allowed me insight into how data analysis is done through the dissection of the lymphoedema data
  • Chapter 1

    Chapter 1

    Parsing Bottom-Up. The only complicated thing is reducing. 1. If the right hand side of the indicated production has k symbols, pop the top k things off the stack (that is, k state-symbol pairs). This is the handle.