Graphs - Chapter 9 Flashcards
1
Q
A blank is a data structure for representing connections among items, and consists of vertices connected by edges
A
graph
2
Q
A blank (or node) represents an item in a graph.
A
vertex
3
Q
An blank represents a connection between two vertices in a graph.
A
edge
4
Q
For a given graph, the number of vertices is commonly represented as blank, and the number of edges as blank
A
V
E
5
Q
Two vertices are blank if connected by an edge.
A
adjacent
6
Q
A blank is a sequence of edges leading from a source (starting) vertex to a destination (ending) vertex.
A
path
7
Q
The blank is the number of edges in the path.
A
path length
8
Q
The blank between two vertices is the number of edges on the shortest path between those vertices
A
distance
9
Q
Blank are often used to represent a geographic map, which can contain information about places and travel routes. Ex: Vertices in a graph can represent airports, with edges representing available flights. Edge weights in such graphs often represent the length of a travel route, either in total distance or expected time taken to navigate the route. Ex: A map service with access to real-time traffic information can assign travel times to road segments.
A
Graphs
10
Q
A graph can be used to represent relationships between products. Blank in the graph corresponding to a customer’s purchased products have adjacent vertices representing products that can be recommended to the customer.
A
Vertices
11
Q
A graph may use a vertex to represent a person. An blank in such a graph represents a relationship between 2 people. In a graph representing a social network, an edge commonly represents friendship. In a graph representing a professional network, an edge commonly represents business conducted between 2 people.
A
edge
12
Q
Various approaches exist for representing a graph data structure. A common approach is an blank.
A
adjacency list
13
Q
two vertices are adjacent if connected by an edge. In an blank graph representation, each vertex has a list of adjacent vertices, each list item representing an edge.
A
adjacency list
14
Q
A key advantage of an adjacency list graph representation is a size of blank, because each vertex appears once, and each edge appears twice. V refers to the number of vertices, E the number of edges.
A
O(V + E)
15
Q
A key disadvantage of an adjacency list graph is that determining whether two vertices are adjacent is blank, because one vertex’s adjacency list must be traversed looking for the other vertex, and that list could have V items.
A
O(V)
16
Q
in most applications, a vertex is only adjacent to a small fraction of the other vertices, yielding a blank. A balnk has far fewer edges than the maximum possible.
A
sparse graph
17
Q
In an blank graph representation, each vertex is assigned to a matrix row and column, and a matrix element is 1 if the corresponding two vertices have an edge or is 0 otherwise.
A
adjacency matrix
18
Q
Assuming the common implementation as a two-dimensional array whose elements are accessible in blank, then an adjacency matrix’s key benefit is O(1) determination of whether two vertices are adjacent: The corresponding element is just checked for 0 or 1.
A
O(1)
19
Q
A key drawback is blank size. Ex: A graph with 1000 vertices would require a 1000 x 1000 matrix, meaning 1,000,000 elements. An adjacency matrix’s large size is inefficient for a sparse graph, in which most elements would be 0’s.
A
O(V^2)
20
Q
An adjacency matrix only represents blank among vertices; if each vertex has data, like a person’s name and address, then a separate list of vertices is needed.
A
edges
21
Q
An algorithm commonly must visit every vertex in a graph in some order, known as a blank.
A
graph traversal
22
Q
A blank is a traversal that visits a starting vertex, then all vertices of distance 1 from that vertex, then of distance 2, and so on, without revisiting a vertex.
A
breadth-first search (BFS)
23
Q
An algorithm for blank enqueues the starting vertex in a queue. While the queue is not empty, the algorithm dequeues a vertex from the queue, visits the dequeued vertex, enqueues that vertex’s adjacent vertices (if not already discovered), and repeats.
A
breadth-first search
24
Q
When the BFS algorithm first encounters a vertex, that vertex is said to have been blank.
A
discovered
25
In the BFS algorithm, the vertices in the queue are called the blank, being vertices thus far discovered but not yet visited. Because each vertex is visited at most once, an already-discovered vertex is not enqueued again.
frontier
26
A blank is a traversal that visits a starting vertex, then visits every vertex along each path starting from that vertex to the path's end before backtracking.
depth-first search (DFS)
27
An algorithm for blank pushes the starting vertex to a stack. While the stack is not empty, the algorithm pops the vertex from the top of the stack. If the vertex has not already been visited, the algorithm visits the vertex and pushes the adjacent vertices to the stack.
depth-first search
28
A blank can be implemented using the program stack instead of an explicit stack. The blank algorithm is first called with the starting vertex. If the vertex has not already been visited, the recursive algorithm visits the vertex and performs a recursive DFS call for each adjacent vertex.
recursive DFS
29
A blank consists of vertices connected by directed edges.
directed graph, or digraph,
30
A blank is a connection between a starting vertex and a terminating vertex.
directed edge
31
In a directed graph, a vertex Y is blank to a vertex X, if there is an edge from X to Y.
adjacent
32
Many graphs are blank, like those representing links between web pages, maps for navigation, or college course prerequisites.
directed
33
In a directed graph: A blank is a sequence of directed edges leading from a source (starting) vertex to a destination (ending) vertex.
path
34
In a directed graph: A blank is a path that starts and ends at the same vertex. A directed graph is cyclic if the graph contains a cycle, and acyclic if the graph does not contain a cycle.
cycle
35
A directed graph is blank if the graph contains a cycle, and blank if the graph does not contain a cycle.
cyclic
acyclic
36
A blank associates a weight with each edge
weighted graph
37
A graph edge's blank, or blank, represents some numerical value between vertex items, such as flight cost between airports, connection speed between computers, or travel time between cities. A weighted graph may be directed or undirected.
weight, or cost,
38
In a weighted graph, the path blank is the sum of the edge weights in the path.
length
39
The blank is the sum of the edge weights in a cycle.
cycle length
40
A blank has a cycle length less than 0
negative edge weight cycle
41
A blank does not exist in a graph with a negative edge weight cycle, because each loop around the negative edge weight cycle further decreases the cycle length, so no minimum exists.
shortest path
42
The Graph class holds a vertex adjacency list using a blank that maps a Vertex object to a list of adjacent Vertex objects. The Vertex class contains a label, but can be augmented by graph algorithms to contain additional data if required.
dictionary
43
A Graph object is initialized with an empty adjacency list. Vertex objects are created and added to the Graph using the blank.
add_vertex() method
44
Edges are represented as vertex pairs, using a blank.
2-item tuple
45
Edges also have blank. By default, an edge is assigned with weight 1.0. Edge weights are stored in the dictionary edge_weights where the vertex pair is the key and the edge weight is the value. Ex: The edge (vertex_a, vertex_b) is assigned with weight 3.7 by self.edge_weights[(vertex_a, vertex_b)] = 3.7.
numeric weights
46
blank traverses a graph by starting at a specific vertex and visiting the vertex's adjacent vertices before visiting the next closest vertices. No vertex is re-visited.
Breadth-first search
47
The breadth-first search function has three parameters:
graph is the graph to search.
start_vertex is the starting vertex of the breadth-first search.
distances is an optional dictionary to store the distance of each visited vertex from the start vertex.
48
The breadth-first search function defines three container variables:
discovered_set is a set of all discovered vertices.
frontier_queue is a Queue variable (Queue class defined in a previous section) that stores vertices that have been discovered, but not yet visited.
visited_list is an ordered list of visited vertices.
49
Initially, the start vertex is added to both blank and blank. start_vertex is dequeued from the queue and added to the visited list. Then, undiscovered vertices adjacent to the current dequeued vertex are added to discovered_set and frontier_queue. The distances from the adjacent vertices are set to the current dequeued vertex's distance + 1.
frontier_queue and discovered_set.
50
The process of dequeuing a vertex from frontier_queue and adding the vertex's adjacent vertices to discovered_set continues until frontier_queue is empty. In the end, blank contains the order of the breadth-first search's traversal.
visited_list
51
Blank search traverses a graph by first visiting a specific starting vertex, and then visiting every vertex along each path originating from the starting vertex. Each path is traversed to the path's end before backtracking.
Depth-first
52
To perform depth-first search, the Graph and Vertex classes are used as well as a depth-first search function. depth_first_search() takes three arguments (the current graph, the starting vertex, and a function to mark visited vertices) and defines two container variables:
vertex_stack is a list used as the stack of yet-to-be-visited vertices.
visited_set is a set used to keep track of which vertices have been visited.
53
Initially, visited_set is empty and the starting vertex is pushed onto blank. So long as vertex_stack is not empty, the loop pops a vertex from vertex_stack and assigns current_vertex with the popped vertex. If current_vertex is not in visited_set, then current_vertex is visited, added to visited_set, and each adjacent vertex is pushed onto vertex_stack.
vertex_stack
54
depth_first_search()'s blank parameter is a function that takes a single vertex as an argument. The function is called once for each vertex traversed during the depth-first search
visit_function
55
Blank computes the shortest path from a given starting vertex to all other vertices in the graph.
Dijkstra's algorithm
56
To perform Dijjkstra's algorithm, the Graph and Vertex classes are used. The Vertex class is extended to include two additional data members:
distance
pred_vertex - A reference to the vertex that occurs immediately before the vertex, on a path from some start vertex to the vertex.
57
Blank - The total sum of the edge weights on a path from some start vertex to the vertex.
distance
58
Blank - A reference to the vertex that occurs immediately before the vertex, on a path from some start vertex to the vertex.
pred_vertex
59
Put all vertices in an unvisited queue.
unvisited_queue = []
for current_vertex in g.adjacency_list:
unvisited_queue.append(current_vertex)
# start_vertex has a distance of 0 from itself
start_vertex.distance = 0
# One vertex is removed with each iteration; repeat until the list is
# empty.
while len(unvisited_queue) > 0:
# Visit vertex with minimum distance from start_vertex
smallest_index = 0
for i in range(1, len(unvisited_queue)):
if unvisited_queue[i].distance < unvisited_queue[smallest_index].distance:
smallest_index = i
current_vertex = unvisited_queue.pop(smallest_index)
# Check potential path lengths from the current vertex to all neighbors.
for adj_vertex in g.adjacency_list[current_vertex]:
edge_weight = g.edge_weights[(current_vertex, adj_vertex)]
alternative_path_distance = current_vertex.distance + edge_weight
# If shorter path from start_vertex to adj_vertex is found,
# update adj_vertex's distance and predecessor
if alternative_path_distance < adj_vertex.distance:
adj_vertex.distance = alternative_path_distance
adj_vertex.pred_vertex = current_vertex
Dijkstra's shortest path algorithm.
60
After calling the dijkstra_shortest_path() function, the shortest path from the starting vertex to any other given vertex can be built by following the pred_vertex blank from the destination vertex to the starting vertex.
backwards
61
Blank, created by Edsger Dijkstra, determines the shortest path from a start vertex to each vertex in a graph.
Dijkstra's shortest path algorithm
62
For each vertex, Dijkstra's algorithm determines the vertex's blank and blank
distance and predecessor pointer
63
A vertex's blank is the shortest path distance from the start vertex.
distance
64
A vertex's blank points to the previous vertex along the shortest path from the start vertex.
predecessor pointer
65
Dijkstra's algorithm initializes all vertices' distances to blank initializes all vertices' predecessors to null, and enqueues all vertices into a queue of unvisited vertices.
infinity (∞),
66
For each adjacent vertex, the algorithm computes the distance of the path from the start vertex to the current vertex and continuing on to the blank. If that path's distance is shorter than the adjacent vertex's current distance, a shorter path has been found. The adjacent vertex's current distance is updated to the distance of the newly found shorter path's distance, and vertex's predecessor pointer is pointed to the current vertex.
adjacent vertex
67
After running Dijkstra's algorithm, the shortest path from the start vertex to a destination vertex can be determined using the vertices' blank
predecessor pointers.
68
If the destination vertex's predecessor pointer is blank, the shortest path is traversed in reverse by following the predecessor pointers until the start vertex is reached.
not 0
69
If the destination vertex's predecessor pointer is null, then a path from the start vertex to the destination vertex blank.
does not exist
70
If the unvisited vertex queue is implemented using a list, the runtime for Dijkstra's shortest path algorithm is blank
O(V^2)
71
Implementing the unvisited vertex queue using a standard binary heap reduces the runtime to BLANK, and using a Fibonacci heap data structure (not discussed in this material) reduces the runtime to blank
O((E + V) log V)
O(E + V log V).
72
Blank can be used for unweighted graphs (using a uniform edge weight of 1) and weighted graphs with non-negative edges weights
Dijkstra's shortest path algorithm
73
For a directed graph with negative edge weights, Dijkstra's algorithm may not find the shortest path for some vertices, so the algorithm should not be used if a blank exists.
negative edge weight
74
The blank, created by Richard Bellman and Lester Ford, Jr., determines the shortest path from a start vertex to each vertex in a graph.
Bellman-Ford shortest path algorithm
75
For each vertex, the Bellman-Ford algorithm determines the vertex's distance and predecessor pointer. A vertex's blank is the shortest path distance from the start vertex.
distance
76
A vertex's blank points to the previous vertex along the shortest path from the start vertex.
predecessor pointer
77
The blank initializes all vertices' current distances to infinity (∞) and predecessors to null, and assigns the start vertex with a distance of 0. The algorithm performs V-1 main iterations, visiting all vertices in the graph during each iteration. Each time a vertex is visited, the algorithm follows all edges to adjacent vertices. For each adjacent vertex, the algorithm computes the distance of the path from the start vertex to the current vertex and continuing on to the adjacent vertex. If that path's distance is shorter than the adjacent vertex's current distance, a shorter path has been found. The adjacent vertex's current distance is updated to the newly found shorter path's distance, and the vertex's predecessor pointer is pointed to the current vertex.
Bellman-Ford algorithm
78
The Bellman-Ford algorithm does not require a blank for visiting vertices during each main iteration. So after each iteration, a vertex's current distance and predecessor may not yet be the shortest path from the start vertex. The shortest path may propagate to only one vertex each iteration, requiring V-1 iterations to propagate from the start vertex to all other vertices.
specific order
79
The runtime for the Bellman-Ford shortest path algorithm is blank. The outer loop (the main iterations) executes V-1 times. In each outer loop execution, the algorithm visits each vertex and follows the subset of edges to adjacent vertices, following a total of E edges across all loop executions.
O(VE)
80
The Bellman-Ford algorithm supports graphs with negative edge weights. However, if a blank exists, a shortest path does not exist. After visiting all vertices V-1 times, the algorithm checks for negative edge weight cycles. If a negative edge weight cycle does not exist, the algorithm returns true (shortest path exists), otherwise returns false.
negative edge weight cycle
81
The Bellman-Ford algorithm computes the shortest path from a given starting vertex to all other vertices in the graph. The algorithm works by first finding the minimum distances for all vertices that are reachable from the start vertex in one step, then in two steps, then in three steps, etc. until minimum distances for all reachable vertices have been calculated. Note that if the graph has |V| vertices, then all minimum distances must be found after at most blank of the main loop.
|V|-1 iterations
82
In the main loop, each edge is examined to see if a blank to the start vertex than was previously known is found. After |V|-1 iterations are complete, a final iteration is performed to see if any distance decreases further; if a distance decreases again, then a negative edge weight cycle must exist in the graph and the algorithm fails.
shorter distance
83
Each Vertex object is assigned two extra data members to help with the Bellman-Ford algorithm:
distance
.
pred_vertex
84
blank- The minimum distance found so far from the start vertex. The data member is assigned with an initial value of float('inf'), which is the Python representation of infinty
.
distance
85
blank - The previous vertex in the shortest path from the start vertex. The data member is assigned with an initial value of None, indicating that at the start of the algorithm, no known path exists from the start vertex.
pred_vertex
86
def bellman_ford(graph, start_vertex):
# Initialize all vertex distances to infinity and
# and predecessor vertices to None.
for current_vertex in graph.adjacency_list:
current_vertex.distance = float('inf') # Infinity
current_vertex.pred_vertex = None
# start_vertex has a distance of 0 from itself
start_vertex.distance = 0
# Main loop is executed |V|-1 times to guarantee minimum distances.
for i in range(len(graph.adjacency_list)-1):
# The main loop.
for current_vertex in graph.adjacency_list:
for adj_vertex in graph.adjacency_list[current_vertex]:
edge_weight = graph.edge_weights[(current_vertex, adj_vertex)]
alternative_path_distance = current_vertex.distance + edge_weight
# If shorter path from start_vertex to adj_vertex is found,
# update adj_vertex's distance and predecessor
if alternative_path_distance < adj_vertex.distance:
adj_vertex.distance = alternative_path_distance
adj_vertex.pred_vertex = current_vertex
# Check for a negative edge weight cycle
for current_vertex in graph.adjacency_list:
for adj_vertex in graph.adjacency_list[current_vertex]:
edge_weight = graph.edge_weights[(current_vertex, adj_vertex)]
alternative_path_distance = current_vertex.distance + edge_weight
# If shorter path from start_vertex to adj_vertex is still found,
# a negative edge weight cycle exists
if alternative_path_distance < adj_vertex.distance:
return False
return True
The bellman_ford() function.
87
A blank of a directed, acyclic graph produces a list of the graph's vertices such that for every edge from a vertex X to a vertex Y, X comes before Y in the list.
topological sort
88
Graphs can be used to indicate a sequence of steps, where an edge from X to Y indicates that X must be done before Y. A blank of such a graph provides one possible ordering for performing the steps. Ex: Given a graph representing course prerequisites, a topological sort of the graph provides an ordering in which the courses can be taken.
topological sort
89
The topological sort algorithm uses three lists:
a results list that will contain a topological sort of vertices, a no-incoming-edges list of vertices with no incoming edges, and a remaining-edges list.
90
The blank starts as an empty list of vertices
result list
91
The blank starts as a list of all vertices in the graph with no incoming edges.
no-incoming-edges vertex list
92
The blank starts as a list of all edges in the graph.
remaining-edges list
93
The algorithm executes while the no-incoming-edges vertex list is not empty. For each iteration, a vertex is removed from the no-incoming-edges list and added to the result list. Next, a temporary list is built by removing all edges in the remaining-edges list that are outgoing from the removed vertex. For each edge currentE in the temporary list, the number of edges in the remaining-edges list that are incoming to currentE's terminating vertex are counted. If the incoming edge count is 0, then currentE's terminating vertex is added to the no-incoming-edges vertex list.
Topological sort algorithm
94
The two vertex lists used in the topological sort algorithm will at most contain all the vertices in the graph. The remaining-edge list will at most contain all edges in the graph. Therefore, for a graph with a set of vertices V and a set of edges E, the space complexity of topological sorting is blank
. If a graph implementation allows for retrieval of a vertex's incoming and outgoing edges in constant time, then the time complexity of topological sorting is also blank
O(|V| + |E|)
95
The blank finds an ordered list of vertices from a directed graph where no vertex has an outgoing edge to a preceding vertex in the list.
topological sort algorithm
96
Blank is useful in many real-world situations such as manufacturing (where some components must be built before other components) or course scheduling (where some courses must be completed as prerequisites to other courses). When the graph is drawn with the vertices lined up left to right in the order of a topological sort, then all edges will point in the direction from left to right.
Topological sorting
97
The topological sorting algorithm iterates through lists of edges. In Python, the Graph class represents edges using a blank in the form: (from_vertex, to_vertex), and a for loop can be used to iterate through a list or set of edges. Ex. Edges are stored in a data member dictionary called edge_weights, so all of the edges in a graph can be iterated through using a loop like:
for (from_vertex, to_vertex) in g.edge_weights.keys():
2-tuple
98
The above code defines two variables that can be used inside the loop body: BLANK AND blank
from_vertex (the start of the edge) and to_vertex (the end of the edge).
99
A set object called edges_remaining is initialized before the main loop with all edges from the graph; a set is used so edges can be removed in blank
time.
O(1)
100
A graph's blank is a subset of the graph's edges that connect all vertices in the graph together with the minimum sum of edge weights.
minimum spanning tree
101
The graph must be blank and blank
weighted and connected
102
A blank graph contains a path between every pair of vertices.
connected
103
Blank determines the subset of a graph's edges that connect all the graph's vertices with the minimum possible sum of edge weights.
Kruskal's minimum spanning tree algorithm
104
Kruskal's minimum spanning tree algorithm uses three collections:
edgeQueue
result
vertexSets:
105
Blank: A priority queue of edges, initially containing all graph edges. Edge weights are priorities.
edgeQueue
106
Blank: A collection of edges comprising the minimum spanning tree, initially empty.
result
107
Blank: A collection of vertex sets. Each set represents vertices connected by edges in result. Initially, vertexSets contains one set for each vertex
vertexSets
108
The Kruskal's minimum spanning tree algorithm executes while blank has at least one edge. In each iteration, the edge with the lowest weight is removed from the edge queue. If the removed edge connects two different vertex sets, then the edge is added to the resulting minimum spanning tree, and the two vertex sets are merged.
edgeQueue
109
Kruskal's minimum spanning tree algorithm's use of the edge list, collection of vertex sets, and resulting edge list results in a space complexity of blank. If the edge list is sorted at the beginning, then the minimum edge can be removed in constant time within the loop. Combined with a mechanism to map a vertex to the containing vertex set in constant time, the minimum spanning tree algorithm has a runtime complexity of blank.
O(|E| + |V|)
O(|E|log|E|)
110
The minimum spanning tree algorithm requires a blank for edges, where each edge's weight is the edge's priority.
priority queue
111
The blank class implements a simple edge object that stores to and from vertices, as well as weight.
EdgeWeight
112
Blank are implemented such that edges are compared to each other using edge weights.
Comparison operators
113
The blank data member is a dictionary that maps a vertex to the set containing the vertex. The get_set() method takes a vertex as an argument and returns the set containing the vertex.
vertex_map
114
The blank takes two different sets as arguments and merges the two together internally. Ex: Suppose 5 vertices, A, B, C, D, and E, are represented in 3 sets in a collection: {A, E}, {B, C}, and {D}. If merge() is called on sets {A, E} and {D}, then the resulting collection contains two sets: {A, E, D} and {B, C}.
merge() method
115
Blank algorithm is implemented in the minimum_spanning_tree() function. A graph is passed as the only argument, and a list of edges representing the graph's minimum spanning tree is returned.
First, edge_list is initialized as a priority queue containing all edges from the graph. Python's heapq module provides a heap-based priority queue implementation, but elements must support comparison. So each object in the queue is an EdgeWeight object.
Next, vertex_sets is initialized as a new VertexSetCollection and result_list is initialized as an empty list. Then the while loop runs as long as vertex_sets has more than one set and edge_list has at least one edge.
During each loop iteration, the edge with the lowest weight is removed from edge_list. set1 is assigned to the set containing the edge's from_vertex and set2 is assigned to the set containing the edge's to_vertex. If the two sets are not the same, the edge is added to result_list and set1 and set2 are merged within vertex_sets.
Kruskal's minimum spanning tree
116
An blank algorithm determines the shortest path between all possible pairs of vertices in a graph.
all pairs shortest path
117
For a graph with vertices V, a blank represents the shortest path lengths between all vertex pairs in the graph. Each row corresponds to a start vertex, and each column in the matrix corresponds to a terminating vertex for each path. Ex: The matrix entry at row F and column T represents the shortest path length from vertex F to vertex T.
|V| x |V| matrix
118
The blank algorithm generates a |V| x |V| matrix of values representing the shortest path lengths between all vertex pairs in a graph.
Floyd-Warshall all-pairs shortest path
119
Graphs with cycles and negative edge weights are supported, but the graph must not have any blank. A blank is a cycle with edge weights that sum to a negative value.
negative cycles
120
The Floyd-Warshall algorithm initializes the shortest path lengths matrix in 3 steps.
Every entry is assigned with infinity.
Each entry representing the path from a vertex to itself is assigned with 0.
For each edge from X to Y in the graph, the matrix entry for the path from X to Y is initialized with the edge's weight.
121
Although only shortest path lengths are computed by the Floyd-Warshall algorithm, the matrix can be used to blank the path sequence. Given the shortest path length from a start vertex to an end vertex is L. An edge from vertex X to the ending vertex exists such that the shortest path length from the starting vertex to X, plus the edge weight, equals L. Each such edge is found, and the path is reconstructed in reverse order.
reconstruct
122
The Floyd-Warshall algorithm builds a |V| x |V| matrix and therefore has a space complexity of blank
. The matrix is constructed with a runtime complexity of blank
.
O(|V|^2)
O(|V|^3)
123
The blank introduced in another section can be extended to assist with implementation of the all pairs shortest path algorithm
Graph class
124
Takes a vertex label as an argument and returns the vertex in the graph with the specified label, or None if no such vertex exists.
get_vertex()
125
Returns a list of all vertices in the graph. The all pairs shortest path algorithm commonly refers to vertices by index, so a linear list of all the graph's vertices is more convenient than the graph's adjacency_list dictionary.
get_vertex_list()
126
Takes a vertex as an argument and returns a list of all edges from the graph that are incoming to that vertex.
get_incoming_edges()
127
The Floyd-Warshall all pairs shortest path algorithm generates a blank of values representing the shortest path lengths between all vertex pairs in a graph. The all_pairs_shortest_path() function returns a list of lists, representing the |V| x |V| matrix of shortest path lengths. The list's length equals the number of vertices in the graph. The length of each list in the list also equals the number of vertices in the graph.
|V| x |V| matrix
128
The matrix returned from all_pairs_shortest_path() can be used to determine the list of edges in the shortest path between two vertices. The reconstruct_path() function takes 4 arguments
graph:
start_vertex
end_vertex
dist_matrix: The distances matrix built by all_pairs_shortest_path().
129
Blank: The graph that the all pairs shortest path matrix was constructed for.
graph
130
blank: Vertex at the start of the path.
start_vertex:
131
Blank: Vertex at the end of the path.
end_vertex
132
Blank: The distances matrix built by all_pairs_shortest_path().
dist_matrix
