What is the goal of today's lecture regarding graphs?
To understand distances and shortest paths in graphs, BFS in directed graphs, and computing shortest paths in weighted graphs using Dijkstra’s algorithm.
What is the shortest path between two nodes in a graph?
Among all paths between two nodes, it is the path that has the smallest total edge weight.
1/18
Flashcards covering distances, shortest paths in graphs and weighted graphs, BFS in directed graphs, and Dijkstra’s algorithm.
Name | Mastery | Learn | Test | Matching | Spaced |
---|
No study sessions yet.
What is the goal of today's lecture regarding graphs?
To understand distances and shortest paths in graphs, BFS in directed graphs, and computing shortest paths in weighted graphs using Dijkstra’s algorithm.
What is the shortest path between two nodes in a graph?
Among all paths between two nodes, it is the path that has the smallest total edge weight.
Name three types of shortest path problems.
Shortest distances (to source), shortest paths (to source), and pathfinding (from source to target).
How can BFS search be used in finding shortest paths?
BFS search can compute shortest paths when the graph is unweighted, even on directed graphs.
Why doesn't BFS work for shortest paths in weighted graphs?
Because BFS tree does not take edge weights into account.
What algorithm can be used to solve shortest path problems on weighted graphs?
Dijkstra’s algorithm.
Name three shortest path problems that Dijkstra's algorithm can solve.
Shortest distances (from source), shortest paths (from source), and pathfinding (from source).
What are the two arrays used in Dijkstra’s algorithm and what do they track?
visited[] which tracks visited nodes, and distanceToSource[] which tracks the distance to the source node.
What's the key idea behind Dijkstra's algorithm for improving distance approximations?
Visit more and more nodes until all distances to the source are accurate.
What is an invariant of Dijkstra's algorithm related to node visits?
When a node is visited, its distance to the source is accurate.
What is the purpose of the previousNode[] array when computing shortest paths using Dijkstra's algorithm?
It stores the previous node in the shortest path from the source to each node.
Briefly outline how pathfinding can be accomplished via Dijkstra's algorithm.
During the algorithm, if the current visited node is the target node, return the distanceToSource[v] and pathToSource[v], where pathToSource[v] = (previousNode[v], previousNode[previousNode[v]], …).
What is the worst-case time complexity of Dijkstra’s Algorithm?
O(n^2)
What is a key requirement for Dijkstra’s algorithm to work correctly regarding edge weights?
All edge weights must be non-negative.
What algorithm can be used if there are edges with negative weights?
Bellman-Ford algorithm (but not negative cycles)
What is the core idea behind the A* search algorithm?
A* uses heuristics (on the distance from current node to specified target) to guide (i.e., be more efficient in) the search
What is the core idea behind the Bellman-Ford algorithm?
Compute (over)estimations of the distances from the source to all other nodes, which you iteratively improve upon (or relax).
How many iterations does Bellman-Ford relax all edges?
n - 1 iterations.
What is the Worst-Case Time Complexity for Bellman-Ford?
O(nm)