University:
Amherst College
Course:
COSC 311 | Algorithms
Academic year:

2024
Views:

312

Pages:

16
Author:

Kronichjfv

Shortest Paths: Dijkstra’s Algorithm SSSP: Context ● Finding the shortest path from a source to goal, or source to every node ● Google/Apple maps Recall: Breadth-First Search ● Finds a path of fewest edges from a source to every reachable node in the graph S I A D* B D C Recall: Breadth-First Search ● Finds a path of fewest edges from a source to every reachable node in the graph I S Destination Path Path length S [S] 0 A [S, A] 1 B [S, A, B] 2 C [S, D, C] 2 D [S, D] 1 I none ∞ A B D C Introduce: Weighted Graphs ● Each edge has a weight, or cost, associated with it I S 1 Destination Path Path cost S [S] 0 A [S, A] 1 B [S, A, B] 2 C [S, D, C] 2 D [S, D] 1 I none ∞ A 1 1 B D 1 C 1 Introduce: Weighted Graphs ● Edge weight could represent a time cost, financial cost, or a relation between two nodes 4.18 SEA Destination Path Path cost SEA [S] 0 ATL [S, A] 4.18 BDL [S, A, B] 6.00 CLE [S, A, B C] 7.13 DUB [S, D] 9.56 I none ∞ ATL 9.56 1.82 BDL DUB 1.13 CLE 6.68 Problem: Breadth-First Search on Weighted Graphs ● BFS is not designed to consider edge weights! Actual shortest path 4.18 SEA BFS path 9.56 ATL 1.82 BDL DUB 1.13 CLE 6.68 Solution: Dijkstra’s Algorithm ● Explore nodes in a greedy, shortest-path-first manner ● Key feature: explore (dequeue/pop) the closest node not yet explored. Pseudocode: With Inefficiencies ● Overview of pseudocode Pseudocode: Addressing Inefficiencies ● Use your Data Structures… Recall: PriorityQueue (Min-Heap Implementation) ● add(Object key, int priority)^ - O(log(n)) ● extractMin() - O(log(n)) ● decreaseKey(Object key, int newPriority)^ - O(log(n))* GYHD: Example Assuming S is the source A 5 S 15 Cost Parent S 0 null A D 2 Destination 7 B B 1 C 6 E 3 D 10 C E 4 i i Conditions for Dijkstra’s ● No negative cycles; a negative cycle will always be a problem ● In fact, no negative edges; a negative edge will sometimes be a problem ● GYHD: come up with a graph that has no negative cycles, has a negative edge, where Dijkstra’s algorithm would not find the shortest path from a source to a destination Counterexample 5 50 S B D 1 -100 101 A If Time: Java implementation ● compareTo(Node other) vs. compare(Node a, Node b) ● Cats ● Time complexity and ease of implementation Finally ● Thank you! ● PLEASE take survey on teaching feedback - will send to you shortly

Shortest Paths Dijkstra’s Algorithm

Related Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock