程序代写代做代考 algorithm data structure PowerPoint Presentation

PowerPoint Presentation

Faculty of Information Technology,
Monash University

FIT2004: Algorithms and Data Structures
Week 8: Introduction to Graphs and Shortest Path Algorithms

These slides are prepared by M. A. Cheema and are based on the material developed by Arun Konagurthu and Lloyd Allison.

Recommended reading
FIT2004, Lec-8: Graphs and Shortest Path Algorithms
Unit notes: Chapters 12&13
Cormen et al. Introduction to Algorithms.
Section 22.1 Representation of graphs
Section 22.2 Breadth-First Search
Section 24.2 Dijkstra’s algorithm
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Graph/
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Graph/Directed/

Outline
FIT2004, Lec-8: Graphs and Shortest Path Algorithms
Introduction to Graphs
Graph Traversal Algorithms
The idea
Breadth First Search (BFS)
Depth First Search (DFS)
Applications
Shortest Path Problem
Breadth First Search (for unweighted graphs)
Dijkstra’s algorithm (for weighted graphs with non-negative weights)

Undirected Graph – Example
FIT2004, Lec-8: Graphs and Shortest Path Algorithms

Directed Graph – Example
FIT2004, Lec-8: Graphs and Shortest Path Algorithms

Undirected Weighted Graph – Example
FIT2004, Lec-8: Graphs and Shortest Path Algorithms

5
4
8
7
6
3
2
5

Directed Weighted Graph – Example
FIT2004, Lec-8: Graphs and Shortest Path Algorithms

5
4
8
7
6
3
2
5

Graphs – Formal notations
FIT2004, Lec-8: Graphs and Shortest Path Algorithms
A graph G = (V, E) is defined using a set of vertices V and a set of edges E.

An edge e is represented as e = (u, v) where u and v are two vertices

For undirected graphs, (u, v) = (v, u) because there is no sense of direction.
For a directed graph, (u, v) represents an edge from u to v and (u, v) ≠ (v, u).

Graphs – Formal notations
FIT2004, Lec-8: Graphs and Shortest Path Algorithms
A weighted graph is represented as G = (V, E, W) where W represents weights for the edges and each edge e is represented as (u, v, w) where w is the weight for the edge (u, v).

A graph is called a simple graph if it does not have loops AND does not contain multiple edges b/w same pair of vertices.

In this unit, we focus on simple graphs.

Some Graph Properties
FIT2004, Lec-8: Graphs and Shortest Path Algorithms
Let G be a graph.
We use V to denote the number of vertices in the graph
We use E to denote the number of edges in the graph
The minimum number of edges in a connected undirected graph
???
The maximum number of edges in a connected undirected graph
???

Quiz time!
https://flux.qa – RFIBMB

Some Graph Properties
FIT2004, Lec-8: Graphs and Shortest Path Algorithms
Let G be a graph.
We use V to denote the number of vertices in the graph
We use E to denote the number of edges in the graph
The minimum number of edges in a connected undirected graph
V-1 = O(V)
The maximum number edges in a connected undirected graph
V(V – 1)/2 = O(V2)

A graph is called sparse if E << V2 (<< means significantly smaller than) A graph is called dense if E ≈ V2 Representing Graphs FIT2004, Lec-8: Graphs and Shortest Path Algorithms Adjacency Matrix: Create a V x V matrix M and store T (true) for M[i][j] if there exists an edge between i-th and j-th vertex. Otherwise, store F (false). 2 1 3 4 5 1 2 3 4 5 1 F T T T F 2 T F T F T 3 T T F F T 4 T F F F T 5 F T T T F Representing Graphs FIT2004, Lec-8: Graphs and Shortest Path Algorithms Adjacency Matrix: Create a V x V matrix M and store weight at M[i][j] only if there exists an edge between i-th and j-th vertex. 1 2 3 4 5 1 2 7 4 2 2 5 6 3 7 5 3 4 4 8 5 6 3 8 2 1 3 4 5 4 8 7 6 3 2 5 Representing Graphs FIT2004, Lec-8: Graphs and Shortest Path Algorithms Adjacency Matrix: Create a V x V matrix M and store weight at M[i][j] only if there exists an edge from i-th to j-th vertex. Space Complexity: O(V2) regardless of the number of edges Time Complexity of checking if an edge exits: O(1) Time Complexity of retrieving all neigbhbors (adjacent vertices) of a given vertex: O(V) regardless of the number of neighbors (unless additional pointers are stored) 1 2 3 4 5 1 7 4 2 2 5 6 3 3 4 8 5 2 1 3 4 5 4 8 7 6 3 2 5 Representing Graphs FIT2004, Lec-8: Graphs and Shortest Path Algorithms Adjacency List: Create an array of size V. At each V[i], store the list of vertices adjacent to the i-th vertex. 2 1 3 4 5 1 2 3 4 5 2 3 4 1 3 5 1 2 5 1 5 2 3 4 Representing Graphs FIT2004, Lec-8: Graphs and Shortest Path Algorithms Adjacency List: Create an array of size V. At each V[i], store the list of vertices adjacent to the i-th vertex along with the weights. The numbers in parenthesis correspond to the weights. 1 2 3 4 5 2 (2) 3 (7) 4 (4) 1 (2) 3 (5) 5 (6) 1 (7) 2 (5) 5 (3) 1 (4) 5 (8) 2 (6) 3 (3) 4 (8) 2 1 3 4 5 4 8 7 6 3 2 5 Representing Graphs FIT2004, Lec-8: Graphs and Shortest Path Algorithms Adjacency List: Create an array of size V. At each V[i], store the list of vertices adjacent to the i-th vertex along with the weights. Space Complexity: O(V + E) Time complexity of checking if a particular edge exists: O(log V) assuming each adjacency list is a sorted array on vertex IDs Time complexity of retrieving all adjacent vertices of a given vertex: O(X) where X is the number of adjacent vertices (note: this is output-sensitive complexity) 1 2 3 4 5 3 (7) 4 (4) 1 (2) 3 (5) 5 (6) 5 (3) 5 (8) 2 1 3 4 5 4 8 7 6 3 2 5 Outline FIT2004, Lec-8: Graphs and Shortest Path Algorithms Introduction to Graphs Graph Traversal Algorithms The idea Breadth First Search (BFS) Depth First Search (DFS) Applications Shortest Path Problem Breadth First Search (for unweighted graphs) Dijkstra’s algorithm (for weighted graphs with non-negative weights) Graph Traversal FIT2004, Lec-8: Graphs and Shortest Path Algorithms Graph traversal algorithms traverse (visit) the nodes of a graph starting from a source vertex. We will look into two algorithms: Breadth First Search (BFS) Depth First Search (DFS) Both of them visit all the vertices of the graph exactly once The order in which they visit vertices is different Each one has properties that make it useful for certain kinds of graph problems B A E F H G D C Graph Traversal - BFS FIT2004, Lec-8: Graphs and Shortest Path Algorithms Breadth First Search (BFS) Traverses the graph uniformly from the source vertex i.e., all vertices that are k edges away from the source vertex are visited before all vertices that are k+1 edges away from source In the graph below, if A is the source, then one possible BFS order is: A, C, B, D, E, F, G, H Is A, B, C, D, E, F, G, H a BFS Order? B A E F H G D C Quiz time! https://flux.qa - RFIBMB Graph Traversal - BFS FIT2004, Lec-8: Graphs and Shortest Path Algorithms Breadth First Search (BFS) Traverses the graph uniformly from the source vertex i.e., all vertices that are k edges away from the source vertex are visited before all vertices that are k+1 edges away from source In the graph below, if A is the source, then one possible BFS order is: A, C, B, D, E, F, G, H Is A, B, C, D, E, F, G, H a BFS Order? Yes! B A E F H G D C Graph Traversal - BFS FIT2004, Lec-8: Graphs and Shortest Path Algorithms Breadth First Search (BFS) Traverses the graph uniformly from the source vertex i.e., all vertices that are k edges away from the source vertex are visited before all vertices that are k+1 edges away from source In the graph below, if A is the source, then one possible BFS order is: A, C, B, D, E, F, G, H Is A, B, C, D, E, F, G, H a BFS Order? Yes! B A E F H G D C Graph Traversal - BFS FIT2004, Lec-8: Graphs and Shortest Path Algorithms Breadth First Search (BFS) Traverses the graph uniformly from the source vertex i.e., all vertices that are k edges away from the source vertex are visited before all vertices that are k+1 edges away from source In the graph below, if A is the source, then one possible BFS order is: A, C, B, D, E, F, G, H Is A, B, C, D, E, F, G, H a BFS Order? Yes! B A E F H G D C Graph Traversal - BFS FIT2004, Lec-8: Graphs and Shortest Path Algorithms Breadth First Search (BFS) Traverses the graph uniformly from the source vertex i.e., all vertices that are k edges away from the source vertex are visited before all vertices that are k+1 edges away from source In the graph below, if A is the source, then one possible BFS order is: A, C, B, D, E, F, G, H Is A, B, C, D, E, F, G, H a BFS Order? Yes! B A E F H G D C Graph Traversal - DFS FIT2004, Lec-8: Graphs and Shortest Path Algorithms Depth First Search (DFS) Traverses the graph as deeply as possible before backtracking and traversing other nodes In the tree, one possible DFS order is: A, B, F, G, H, E, C, D Is A, B, E, H, F, G, C, D as possible DFS order? B A E F H G D C Quiz time! https://flux.qa - RFIBMB Graph Traversal - DFS FIT2004, Lec-8: Graphs and Shortest Path Algorithms Depth First Search (DFS) Traverses the graph as deeply as possible before backtracking and traversing other nodes In the tree, one possible DFS order is: A, B, F, G, H, E, C, D Is A, B, E, H, F, G, C, D as possible DFS order? No! B A E F H G D C Graph Traversal - DFS FIT2004, Lec-8: Graphs and Shortest Path Algorithms Depth First Search (DFS) Traverses the graph as deeply as possible before backtracking and traversing other nodes In the tree, one possible DFS order is: A, B, F, G, H, E, C, D Is A, B, E, H, F, G, C, D as possible DFS order? No! B A E F H G D C Graph Traversal - DFS FIT2004, Lec-8: Graphs and Shortest Path Algorithms Depth First Search (DFS) Traverses the graph as deeply as possible before backtracking and traversing other nodes In the tree, one possible DFS order is: A, B, F, G, H, E, C, D Is A, B, E, H, F, G, C, D as possible DFS order? No! B A E F H G D C Graph Traversal - DFS FIT2004, Lec-8: Graphs and Shortest Path Algorithms Depth First Search (DFS) Traverses the graph as deeply as possible before backtracking and traversing other nodes In the tree, one possible DFS order is: A, B, F, G, H, E, C, D Is A, B, E, H, F, G, C, D as possible DFS order? No! B A E F H G D C Graph Traversal - DFS FIT2004, Lec-8: Graphs and Shortest Path Algorithms Depth First Search (DFS) Traverses the graph as deeply as possible before backtracking and traversing other nodes In the tree, one possible DFS order is: A, B, F, G, H, E, C, D Is A, B, E, H, F, G, C, D as possible DFS order? No! B A E F H G D C Graph Traversal - DFS FIT2004, Lec-8: Graphs and Shortest Path Algorithms Depth First Search (DFS) Traverses the graph as deeply as possible before backtracking and traversing other nodes In the tree, one possible DFS order is: A, B, F, G, H, E, C, D Is A, B, E, H, F, G, C, D as possible DFS order? No! B A E F H G D C Graph Traversal - DFS FIT2004, Lec-8: Graphs and Shortest Path Algorithms Depth First Search (DFS) Traverses the graph as deeply as possible before backtracking and traversing other nodes In the tree, one possible DFS order is: A, B, F, G, H, E, C, D Is A, B, E, H, F, G, C, D as possible DFS order? No! B A E F H G D C Graph Traversal - DFS FIT2004, Lec-8: Graphs and Shortest Path Algorithms Depth First Search (DFS) Traverses the graph as deeply as possible before backtracking and traversing other nodes In the tree, one possible DFS order is: A, B, F, G, H, E, C, D Is A, B, E, H, F, G, C, D as possible DFS order? No! B A E F H G D C Outline FIT2004, Lec-8: Graphs and Shortest Path Algorithms Introduction to Graphs Graph Traversal Algorithms The idea Breadth First Search (BFS) Depth First Search (DFS) Applications Shortest Path Problem Breadth First Search (for unweighted graphs) Dijkstra’s algorithm (for weighted graphs with non-negative weights) Breadth First Search (BFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Queue: Visited: In Queue: Visited: B A E F H G D C Current: Note! The visualisation of discovered and visited does not correspond to implementation. See complexity discussion for optimised implementation A A Current: Breadth First Search (BFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Queue: Visited: B A E F H G D C Current: A A In Queue: Visited: Current: Breadth First Search (BFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Queue: Visited: B A E F H G D C Current: A A B C In Queue: Visited: Current: Breadth First Search (BFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Queue: Visited: B A E F H G D C Current: B A B C Breadth First Search (BFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Queue: Visited: B A E F H G D C Current: B C In Queue: Visited: Current: A B Breadth First Search (BFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Queue: Visited: B A E F H G D C Current: B A B C E F In Queue: Visited: Current: Breadth First Search (BFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Queue: Visited: B A E F H G D C Current: C A B C E F In Queue: Visited: Current: Breadth First Search (BFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Queue: Visited: B A E F H G D C Current: C A B C E F D Breadth First Search (BFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Queue: Visited: B A E F H G D C Current: E A B C E F D In Queue: Visited: Current: Breadth First Search (BFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Queue: Visited: B A E F H G D C Current: E A B C E F D G H In Queue: Visited: Current: Breadth First Search (BFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Queue: Visited: B A E F H G D C Current: F A B C E F D G H In Queue: Visited: Current: Breadth First Search (BFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Queue: Visited: B A E F H G D C Current: D A B C E F D G H In Queue: Visited: Current: Breadth First Search (BFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Queue: Visited: B A E F H G D C Current: G A B C E F D G H In Queue: Visited: Current: Breadth First Search (BFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Queue: Visited: B A E F H G D C Current: H A B C E F D G H In Queue: Visited: Current: Breadth First Search (BFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: B A E F H G D C Current: A B C E F D G H Queue: Breadth First Search (BFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Initialize some data structure “queue” and some data structure “visited”, both empty of vertices Put an initial vertex in queue Mark the initial vertex as visited While queue is not empty Get the first vertex, u, from queue For each edge (u,v) If v is not visited Add v to visited add v at the end of queue Quiz time! https://flux.qa - RFIBMB Breadth First Search (BFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Initialize some data structure “queue” and some data structure “visited”, both empty of vertices Put an initial vertex in queue Mark the initial vertex as visited While queue is not empty Get the first vertex, u, from queue For each edge (u,v) If v is not visited Add v to visited add v at the end of queue Assuming adjacency list representation. Time Complexity: We look at every edge twice For each edge, we do a lookup on visited (with some complexity) We insert vertices to visited at most O(V) times O(V*insert to visited + E*lookup on visited) Breadth First Search (BFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Initialize some data structure “queue” and some data structure “visited”, both empty of vertices Put an initial vertex in queue Mark the initial vertex as visited While queue is not empty Get the first vertex, u, from queue For each edge (u,v) If v is not visited Add v to visited add v at the end of queue Assuming adjacency list representation. Time Complexity: O(V*insert to visited + E*lookup on visited) Visited it just a bit list, indexed by vertex ID Lookup and insert are both O(1) Breadth First Search (BFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Initialize some data structure “queue” and some data structure “visited”, both empty of vertices Put an initial vertex in queue Mark the initial vertex as visited While queue is not empty Get the first vertex, u, from queue For each edge (u,v) If v is not visited Add v to visited add v at the end of queue Assuming adjacency list representation. Time Complexity: O(V * 1 + E * 1) = O(V+E) Space Complexity: O(V+E) Breadth First Search (BFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Assuming adjacency list representation. Time Complexity: O(V+E) Space Complexity: O(V+E) Outline FIT2004, Lec-8: Graphs and Shortest Path Algorithms Introduction to Graphs Graph Traversal Algorithms The idea Breadth First Search (BFS) Depth First Search (DFS) Applications Shortest Path Problem Breadth First Search (for unweighted graphs) Dijkstra’s algorithm (for weighted graphs with non-negative weights) Example with good data structures FIT2004, Lec-8: Graphs and Shortest Path Algorithms Now that you have the idea of BFS And we have seen how to use a bit list to make it faster We will do the DFS example with a bit list BFS should also use a bit list, the example above was just for intuition! Depth First Search (DFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Visited: B A E F H G D C Current: A B C D E F G H 0 0 0 0 0 0 0 0 A Visited is indexed by vertex ID. Normally, the IDs are integers from from 0 to V-1 (to allows O(1) lookup), but letters are used here for ease of understanding Depth First Search (DFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Visited: B A E F H G D C Current: A B C D E F G H 1 0 0 0 0 0 0 0 A 1 Depth First Search (DFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Visited: B A E F H G D C Current: A B C D E F G H 1 0 0 0 0 0 0 0 A 1 Depth First Search (DFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Visited: B A E F H G D C Current: A B C D E F G H 1 1 0 0 0 0 0 0 B 1 2 Depth First Search (DFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Visited: B A E F H G D C Current: A B C D E F G H 1 1 0 0 0 0 0 0 B 1 2 Depth First Search (DFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Visited: B A E F H G D C Current: A B C D E F G H 1 1 0 0 1 0 0 0 E 1 2 3 Depth First Search (DFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Visited: B A E F H G D C Current: A B C D E F G H 1 1 0 0 1 0 0 0 E 1 2 3 Depth First Search (DFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Visited: B A E F H G D C Current: A B C D E F G H 1 1 0 0 1 0 1 0 G 1 2 3 4 Depth First Search (DFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Visited: B A E F H G D C Current: A B C D E F G H 1 1 0 0 1 0 1 0 G 1 2 3 4 Depth First Search (DFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Visited: B A E F H G D C Current: A B C D E F G H 1 1 0 0 1 1 1 0 F 1 2 3 4 5 Depth First Search (DFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Visited: B A E F H G D C Current: A B C D E F G H 1 1 0 0 1 1 1 0 F 1 2 3 4 5 Depth First Search (DFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Visited: B A E F H G D C Current: A B C D E F G H 1 1 0 0 1 1 1 0 F 1 2 3 4 5 Depth First Search (DFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Visited: B A E F H G D C Current: A B C D E F G H 1 1 0 0 1 1 1 0 F 1 2 3 4 5 We have checked all neighbours of F It is a dead end Go back to the last active node (G) Depth First Search (DFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Visited: B A E F H G D C Current: A B C D E F G H 1 1 0 0 1 1 1 0 G 1 2 3 4 5 Depth First Search (DFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Visited: B A E F H G D C Current: A B C D E F G H 1 1 0 0 1 1 1 0 G 1 2 3 4 5 Depth First Search (DFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Visited: B A E F H G D C Current: A B C D E F G H 1 1 0 0 1 1 1 0 G 1 2 3 4 5 Depth First Search (DFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Visited: B A E F H G D C Current: A B C D E F G H 1 1 0 0 1 1 1 1 H 1 2 3 4 5 6 Depth First Search (DFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Visited: B A E F H G D C Current: A B C D E F G H 1 1 0 0 1 1 1 1 H Speeding up visualisation… 1 2 3 4 5 6 Depth First Search (DFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Visited: B A E F H G D C Current: A B C D E F G H 1 1 0 0 1 1 1 1 H 1 2 3 4 5 6 H is a dead end Going back to G, it is also a dead end Go back to E Depth First Search (DFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Visited: B A E F H G D C Current: A B C D E F G H 1 1 0 0 1 1 1 1 E 1 2 3 4 5 6 Depth First Search (DFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Visited: B A E F H G D C Current: A B C D E F G H 1 1 0 0 1 1 1 1 B 1 2 3 4 5 6 Depth First Search (DFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Visited: B A E F H G D C Current: A B C D E F G H 1 1 0 0 1 1 1 1 A 1 2 3 4 5 6 Depth First Search (DFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Visited: B A E F H G D C Current: A B C D E F G H 1 1 1 0 1 1 1 1 C 1 2 3 4 5 6 7 Depth First Search (DFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Visited: B A E F H G D C Current: A B C D E F G H 1 1 1 0 1 1 1 1 C 1 2 3 4 5 6 7 Depth First Search (DFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Visited: B A E F H G D C Current: A B C D E F G H 1 1 1 1 1 1 1 1 D 1 2 3 4 5 6 7 8 Depth First Search (DFS) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Assuming adjacency list representation. Time Complexity: Each vertex visited at most once Each edge accessed at most twice (once when u is visited once when v is visited) Total cost: O(V+E) Space Complexity: O(V + E) Outline FIT2004, Lec-8: Graphs and Shortest Path Algorithms Introduction to Graphs Graph Traversal Algorithms The idea Breadth First Search (BFS) Depth First Search (DFS) Applications Shortest Path Problem Breadth First Search (for unweighted graphs) Dijkstra’s algorithm (for weighted graphs with non-negative weights) Applications of DFS and BFS FIT2004, Lec-8: Graphs and Shortest Path Algorithms The algorithms we saw can also be applied on directed graphs. BFS and DFS have a wide variety of applications Reachability Finding all connected components Finding cycles Topological sort (week 11) Shortest paths on unweighted graphs … More details are given in unit notes and tutorials B A E F H G D C Shortest Path Problem FIT2004, Lec-8: Graphs and Shortest Path Algorithms Length of a path: For unweighted graphs, the length of a path is the number of edges along the path. For weighted graphs, the length of a path is the sum of weights of the edges along the path. Shortest Path Problem FIT2004, Lec-8: Graphs and Shortest Path Algorithms Single sources single target: Given a source vertex s and a target vertex t, return the shortest path from s to t. Single source all targets: Given a source vertex s, return the shortest paths to every other vertex in the graph. We will focus on single source all targets problem because the single source single target problem is subsumed by it. Shortest Path Algorithms FIT2004, Lec-8: Graphs and Shortest Path Algorithms Breadth First Search – (Single source, unweighted graphs) Dijkstra’s Algorithm – (Single Source, weighted graphs with only non-negative weights) Bellman Ford Algorithm – (Single source, weighted graphs including negative weights) Floyd-Warshall Algorithm– (All pairs, weighted graphs including negative weights) Outline FIT2004, Lec-8: Graphs and Shortest Path Algorithms Introduction to Graphs Graph Traversal Algorithms Breadth First Search (BFS) Depth First Search (DFS) Applications Shortest Path Problem Breadth First Search (for unweighted graphs) Dijkstra’s algorithm (for weighted graphs with non-negative weights) BFS shortest path (now with good data structures) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Discovered: Visited: B A E F H G D C u (current): A B C D E F G H 1 0 0 0 0 0 0 0 A Queue: Dist: 0 BFS shortest path (now with good data structures) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Discovered: Visited: B A E F H G D C u (current): A B C D E F G H 1 0 0 0 0 0 0 0 A Queue: Dist: 0 BFS shortest path (now with good data structures) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Discovered: Visited: B A E F H G D C u (current): A B C D E F G H 1 0 0 0 0 0 0 0 A Queue: Dist: 0 Dist: 1 BFS shortest path (now with good data structures) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Discovered: Visited: B A E F H G D C u (current): A B C D E F G H 1 1 0 0 0 0 0 0 B A Queue: Dist: 0 Dist: 1 Dist: 1 BFS shortest path (now with good data structures) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Discovered: Visited: B A E F H G D C u (current): A B C D E F G H 1 1 1 0 0 0 0 0 B C A Queue: Dist: 0 Dist: 1 Dist: 1 BFS shortest path (now with good data structures) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Discovered: Visited: B A E F H G D C u (current): A B C D E F G H 1 1 1 0 0 0 0 0 C B Queue: Dist: 0 Dist: 1 Dist: 1 BFS shortest path (now with good data structures) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Discovered: Visited: B A E F H G D C u (current): A B C D E F G H 1 1 1 0 0 0 0 0 C B Queue: Dist: 0 Dist: 1 Dist: 1 Dist: 2 BFS shortest path (now with good data structures) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Discovered: Visited: B A E F H G D C u (current): A B C D E F G H 1 1 1 0 1 0 0 0 C E B Queue: Dist: 0 Dist: 1 Dist: 1 Dist: 0 Dist: 1 Dist: 1 Dist: 2 Dist: 2 BFS shortest path (now with good data structures) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Discovered: Visited: B A E F H G D C u (current): A B C D E F G H 1 1 1 0 1 1 0 0 C E F B Queue: Dist: 0 Dist: 1 Dist: 1 Dist: 2 Dist: 2 BFS shortest path (now with good data structures) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Discovered: Visited: B A E F H G D C u (current): A B C D E F G H 1 1 1 0 1 1 0 0 C E F B Queue: Dist: 0 Dist: 1 Dist: 1 Dist: 2 Dist: 2 BFS shortest path (now with good data structures) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Discovered: Visited: B A E F H G D C u (current): A B C D E F G H 1 1 1 0 1 1 0 0 E F Queue: C Dist: 0 Dist: 1 Dist: 1 Dist: 2 Dist: 2 BFS shortest path (now with good data structures) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Discovered: Visited: B A E F H G D C u (current): A B C D E F G H 1 1 1 0 1 1 0 0 E F Queue: C Dist: 0 Dist: 1 Dist: 1 Dist: 2 Dist: 2 BFS shortest path (now with good data structures) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Discovered: Visited: B A E F H G D C u (current): A B C D E F G H 1 1 1 1 1 1 0 0 E F D Queue: C Dist: 0 Dist: 1 Dist: 1 Dist: 2 Dist: 2 Dist: 2 BFS shortest path (now with good data structures) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Discovered: Visited: B A E F H G D C u (current): A B C D E F G H 1 1 1 1 1 1 0 0 E F D Queue: C Dist: 0 Dist: 1 Dist: 1 Dist: 2 Dist: 2 Dist: 2 BFS shortest path (now with good data structures) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Discovered: Visited: B A E F H G D C u (current): A B C D E F G H 1 1 1 1 1 1 0 0 F D Queue: E Dist: 0 Dist: 1 Dist: 1 Dist: 2 Dist: 2 Dist: 2 BFS shortest path (now with good data structures) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Discovered: Visited: B A E F H G D C u (current): A B C D E F G H 1 1 1 1 1 1 0 0 F D Queue: E Dist: 0 Dist: 1 Dist: 1 Dist: 2 Dist: 2 Dist: 2 BFS shortest path (now with good data structures) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Discovered: Visited: B A E F H G D C u (current): A B C D E F G H 1 1 1 1 1 1 1 1 F D G H Queue: E Dist: 0 Dist: 1 Dist: 1 Dist: 2 Dist: 2 Dist: 2 Dist: 3 Dist: 3 BFS shortest path (now with good data structures) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Discovered: Visited: B A E F H G D C u (current): A B C D E F G H 1 1 1 1 1 1 1 1 D G H Queue: F Dist: 0 Dist: 1 Dist: 1 Dist: 2 Dist: 2 Dist: 3 Dist: 3 Dist: 2 BFS shortest path (now with good data structures) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Discovered: Visited: B A E F H G D C u (current): A B C D E F G H 1 1 1 1 1 1 1 1 G H Queue: D Dist: 0 Dist: 1 Dist: 1 Dist: 2 Dist: 2 Dist: 3 Dist: 3 Dist: 2 BFS shortest path (now with good data structures) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Discovered: Visited: B A E F H G D C u (current): A B C D E F G H 1 1 1 1 1 1 1 1 G H Queue: D Dist: 0 Dist: 1 Dist: 1 Dist: 2 Dist: 2 Dist: 3 Dist: 3 Dist: 2 BFS shortest path (now with good data structures) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Discovered: Visited: B A E F H G D C u (current): A B C D E F G H 1 1 1 1 1 1 1 1 H Queue: G Dist: 0 Dist: 1 Dist: 1 Dist: 2 Dist: 2 Dist: 3 Dist: 3 Dist: 2 BFS shortest path (now with good data structures) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Discovered: Visited: B A E F H G D C u (current): A B C D E F G H 1 1 1 1 1 1 1 1 H Queue: G Dist: 0 Dist: 1 Dist: 1 Dist: 2 Dist: 2 Dist: 3 Dist: 3 Dist: 2 BFS shortest path (now with good data structures) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Discovered: Visited: B A E F H G D C u (current): A B C D E F G H 1 1 1 1 1 1 1 1 Queue: H Dist: 0 Dist: 1 Dist: 1 Dist: 2 Dist: 2 Dist: 3 Dist: 3 Dist: 2 BFS shortest path (now with good data structures) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Discovered: Visited: B A E F H G D C u (current): A B C D E F G H 1 1 1 1 1 1 1 1 Queue: H Dist: 0 Dist: 1 Dist: 1 Dist: 2 Dist: 2 Dist: 3 Dist: 3 Dist: 2 BFS shortest path (now with good data structures) FIT2004, Lec-8: Graphs and Shortest Path Algorithms Visited: Discovered: Visited: B A E F H G D C u (current): A B C D E F G H 1 1 1 1 1 1 1 1 Queue: Dist: 0 Dist: 1 Dist: 1 Dist: 2 Dist: 2 Dist: 3 Dist: 3 Dist: 2 Unweighted shortest paths FIT2004, Lec-8: Graphs and Shortest Path Algorithms Note that distances are stored in an O(1) lookup structure Complexity is the same as regular BFS, O(V+E) Distances are set by lookup at the distance of the current vertex and adding 1 Outline FIT2004, Lec-8: Graphs and Shortest Path Algorithms Introduction to Graphs Graph Traversal Algorithms The idea Breadth First Search (BFS) Depth First Search (DFS) Applications Shortest Path Problem Breadth First Search (for unweighted graphs) Dijkstra’s algorithm (for weighted graphs with non-negative weights) Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms C B E D A 10 5 2 3 1 9 2 4 6 Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms C B A 10 5 0 10? 5? Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms C B E D A 10 5 3 9 2 0 5 10? Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms C B E D A 10 5 3 9 2 0 5 14? 8? 7? Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms Pred: Dist: C B E D A 10 5 2 3 1 9 2 4 6 Q: A B C D E 0 Inf Inf Inf inf A B C D E - - - - - A B C D E 0 Inf Inf Inf Inf Q is a priority queue, where priority is based on distance Pred and Dist are the usual ID-indexed arrays u: Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms Pred: Dist: C B E D A 10 5 2 3 1 9 2 4 6 Q: A B C D E 0 Inf Inf Inf inf B C D E Inf Inf Inf Inf Q is a priority queue, where priority is based on distance Pred and Dist are the usual ID-indexed arrays u: A A B C D E - - - - - Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms Pred: Dist: C B E D A 10 5 2 3 1 9 2 4 6 Q: A B C D E 0 Inf Inf Inf inf B C D E Inf Inf Inf Inf For each neighbour v of u, relax along that edge If dist[u] + w(u,v) < dist[v] Update dist[v] Set pred[v] = u u: A A B C D E - - - - - Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms Pred: Dist: C B E D A 10 5 2 3 1 9 2 4 6 Q: A B C D E 0 Inf 5 Inf inf A B C D E - - A - - C B D E 5 Inf Inf Inf For each neighbour v of u, relax along that edge If dist[u] + w(u,v) < dist[v] Update dist[v] Set pred[v] = u 0 + 5 < inf Set dist[C] = 5 Set pred[C] = A Note that this changes the order of Q u: A Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms Pred: Dist: C B E D A 10 5 2 3 1 9 2 4 6 Q: A B C D E 0 10 5 Inf inf C B D E 5 10 Inf Inf u: A Doing the same for B 0 + 10 < inf Dist[B] = 10 A B C D E - - A - - Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms Pred: Dist: C B E D A 10 5 2 3 1 9 2 4 6 Q: A B C D E 0 10 5 Inf inf C B D E 5 10 Inf Inf u: A Doing the same for B 0 + 10 < inf Dist[B] = 10 Pred[B] = A A B C D E - A A - - Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms Pred: Dist: C B E D A 10 5 2 3 1 9 2 4 6 Q: A B C D E 0 10 5 Inf inf C B D E 5 10 Inf Inf u: A Finished with A, so pop from Q Notice that this will always be the vertex with the smallest dist A B C D E - A A - - Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms Pred: Dist: C B E D A 10 5 2 3 1 9 2 4 6 Q: A B C D E 0 10 5 Inf inf B D E 10 Inf Inf u: C Finished with A, so pop from Q Notice that this will always be the vertex with the smallest dist The dist of this vertex is now finalised A B C D E - A A - - Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms Pred: Dist: C B E D A 10 5 2 3 1 9 2 4 6 Q: A B C D E 0 10 5 Inf inf B D E 10 Inf Inf u: C Relax B from C Dist[C] + w(C, B) = 5 + 3 < 10 Dist[B] = 8 Pred[B] = C A B C D E - A A - - Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms Pred: Dist: C B E D A 10 5 2 3 1 9 2 4 6 Q: A B C D E 0 8 5 Inf inf B D E 8 Inf Inf u: C Relax B from C Dist[C] + w(C, B) = 5 + 3 < 10 Dist[B] = 8 Pred[B] = C A B C D E - C A - - Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms Pred: Dist: C B E D A 10 5 2 3 1 9 2 4 6 Q: A B C D E 0 8 5 Inf inf B D E 8 Inf Inf u: C Relax E from C Dist[C] + w(C, E) = 5 + 2 < Inf Dist[E] = 7 Pred[E] = C A B C D E - C A - - Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms Pred: Dist: C B E D A 10 5 2 3 1 9 2 4 6 Q: A B C D E 0 8 5 Inf 7 u: C Relax E from C Dist[C] + w(C, E) = 5 + 2 < Inf Dist[E] = 7 Pred[E] = C A B C D E - C A - C E B D 7 8 inf Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms Pred: Dist: C B E D A 10 5 2 3 1 9 2 4 6 Q: A B C D E 0 8 5 14 7 u: C Relax D from C Dist[D] + w(C, D) = 5 + 9 < Inf Dist[D] = 14 Pred[D] = C A B C D E - C A C C E B D 7 8 14 Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms Pred: Dist: C B E D A 10 5 2 3 1 9 2 4 6 Q: A B C D E 0 8 5 14 7 E B D 7 8 14 u: C Done with C Pop another vertex from Q and finalise it A B C D E - C A C C Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms Pred: Dist: C B E D A 10 5 2 3 1 9 2 4 6 Q: A B C D E 0 8 5 14 7 u: E A B C D E - C A C C B D 8 14 Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms Pred: Dist: C B E D A 10 5 2 3 1 9 2 4 6 Q: u: E Relax from E A B C D E - C A E C B D 8 13 A B C D E 0 8 5 13 7 Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms Pred: Dist: C B E D A 10 5 2 3 1 9 2 4 6 Q: u: B Done with E Pop B A B C D E - C A E C D 13 A B C D E 0 8 5 13 7 Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms Pred: Dist: C B E D A 10 5 2 3 1 9 2 4 6 Q: u: B Relax from B A B C D E - C A B C D 9 A B C D E 0 8 5 9 7 Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms Pred: Dist: C B E D A 10 5 2 3 1 9 2 4 6 Q: u: D Done with B Pop D No neighbours to relax Done! A B C D E - C A B C A B C D E 0 8 5 9 7 Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms Pred: Dist: C B E D A 10 5 2 3 1 9 2 4 6 Q: u: D A B C D E - C A B C A B C D E 0 8 5 9 7 Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms Pred: Dist: C B E D A 10 5 2 3 1 9 2 4 6 Q: u: D A B C D E - C A B C A B C D E 0 8 5 9 7 Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms Pred: Dist: C B E D A 10 5 2 3 1 9 2 4 6 Q: A B C D E - C A B C A B C D E 0 8 5 9 7 C B E D A 5 3 1 2 Dijkstra’s Algorithm Quiz time! https://flux.qa - RFIBMB Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms Time Complexity: Each edge visited once  O(E) Relaxation is O(1) since we can find distances and compare them in O(1) Updating the priority queue: depends on implementation While loop executes O(V) times Find the vertex with smallest distance: depends on priortiy queue implementation Total cost: O(E*Q.decrease_key + V *Q.extract_min) Dijkstra’s Algorithm using min-heap FIT2004, Lec-8: Graphs and Shortest Path Algorithms Required additional structure: Create an array called Vertices. Vertices[i] will record the location of i-th vertex in the min-heap Updating the distance of a vertex v in min-heap in O(log V) Find the location in the queue (heap) in O(1) using Vertices Now do the normal heap-up operation in O(log(V)) For each swap performed between two vertices x and y during the upHeap Update Vertices[x] and Vertices[y] to record their updated locations in the min-heap Dijkstra’s Algorithm using min-heap FIT2004, Lec-8: Graphs and Shortest Path Algorithms Suppose K’s distance is to be updated to 7. 4 9 11 15 18 13 14 1 2 3 4 5 6 7 Min-heap Vertices 4 9 15 18 11 13 14 1 2 3 4 5 6 7 - 2 5 - 3 - - 7 - 4 6 1 A B C D E F G H I J K L 1 2 3 4 5 6 7 8 9 10 11 12 L B E C J K H Example worked by hand in lecture L B E J C K H Time Complexity of Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms Time Complexity: Each edge visited once  O(E) Relaxation is O(1) since we can find distances and compare them in O(1) Updating the priority queue: depends on implementation While loop executes O(V) times Find the vertex with smallest distance: depends on priortiy queue implementation Total cost: O(E*Q.decrease_key + V *Q.extract_min) Time Complexity of Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms Time Complexity: Each edge visited once  O(E) Relaxation is O(1) since we can find distances and compare them in O(1) Updating the priority queue: O(logV) While loop executes O(V) times Find the vertex with smallest distance: O(1) Total cost: O(E*Q.decrease_key + V *Q.extract_min) Total cost: O(E*logV+ V *logV) Minimum value of E is V-1 since graph is connected E dominates V Total cost O(ElogV) Time Complexity of Dijkstra’s Algorithm FIT2004, Lec-8: Graphs and Shortest Path Algorithms O(E log V) For dense graphs, E ≈ V2 O(E log V)  O(V2 log V) for dense graphs Dijkstra’s using a Fibonacci Heap (not covered in this unit) O(E + V log V) For dense graphs, E ≈ V2 O(E + V log V)  O(V2) for dense graphs Proof of Correctness FIT2004, Lec-8: Graphs and Shortest Path Algorithms Claim: For every vertex v which has been removed from the queue, dist[v] is correct Notation: V is the set of vertices Q is the set of vertices in the queue S = V / Q = the set of vertices who have been removed from the queue Base Case Dist[s] is initialised to 0, which is the shortest distance from s to s (since there are no negative weights) Proof of Correctness FIT2004, Lec-8: Graphs and Shortest Path Algorithms b a c u s Claim: For every vertex v which has been removed from the queue, dist[v] is correct Inductive Step: Assume that the claim holds for all vertices which have been removed from the queue (S) Let u be the next vertex which is removed from the queue We will show that dist[u] is correct d Still in queue Removed from queue Proof of Correctness FIT2004, Lec-8: Graphs and Shortest Path Algorithms x a c u s Claim: For every vertex v which has been removed from the queue, dist[v] is correct Inductive Step: Suppose (for contradiction) there is a shorter path P, s⟿u with len(P) < dist[u] Let x be the furthest vertex on P which is in S (i.e. has been finalised) By the inductive hypothesis, dist[x] is correct (since it is in S) d Current path Assumed shorter path (P) Proof of Correctness FIT2004, Lec-8: Graphs and Shortest Path Algorithms Claim: For every vertex v which has been removed from the queue, dist[v] is correct Inductive Step: By the inductive hypothesis, dist[x] is correct (since it is in S) Let y be the next vertex on P after x Len(P) < dist[u] (by assumption) Edge weights are non-negative Len(s⟿y) <= len(P) < dist[u] x a y u s d Proof of Correctness FIT2004, Lec-8: Graphs and Shortest Path Algorithms Claim: For every vertex v which has been removed from the queue, dist[v] is correct Inductive Step: Len(s⟿y) <= len(P) < dist[u] Since we said that P (via x and y) is a shortest path… dist[y] = len(s⟿y) < dist[u] So dist[y] < dist[u]… If y ≠ u, why didn’t y get removed before u??? If y = u, how can dist[y] new
Swap parent and new element

4 9 11 15 18 13 14 17 19 23 20

1 2 3 4 5 6 7 8 9 10 11 12