Tags: connected components, breadth first search, shortest paths
Suppose you are about to run a BFS on a graph whose exact edge structure you do not know. However, you do know that the graph is undirected, has 8 nodes, and has 2 connected components.
You have picked a node to start on and are about to run a BFS to find shortest path distances. What is the greatest shortest path distance between the starting node and any other node that could possibly be found in such a graph? Hint: consider how large a connected component could possibly be.
Answer: 6. The largest a connected component can be is 7 nodes (the other component must have at least one node). If those 7 nodes form a path and we start at one end, the node at the other end is at distance 6.
Tags: breadth first search, shortest paths
Suppose that a breadth-first search on an undirected graph \(G\) is paused and the queue is printed. Suppose that every node in the queue is either distance 5 from the source, or distance 6. At this moment, node \(u\) is undiscovered.
True or False: it is possible that node \(u\) is distance 4 from the source.
False.
BFS pops nodes in order of distance, so if every node in the queue is at distance 5 or more, every node at distance 4 has already been popped. That means it was discovered earlier, so it can't be undiscovered now.
Tags: breadth first search, shortest paths
Consider the following problem: you're given an unweighted graph \(G\), a source node \(u\), a destination node \(v\), and an "intermediate" node \(x\). Your goal is to find a shortest path from \(u\) to \(v\) that passes through \(x\).
Your friend proposes the following algorithm: run a BFS starting at node \(u\), then terminate it when it reaches node \(x\). Then start a BFS at node \(x\), and terminate it when it reaches node \(v\).
Does this algorithm work?
Yes. Any path from \(u\) to \(v\) through \(x\) consists of a path from \(u\) to \(x\) followed by a path from \(x\) to \(v\), so its length is at least the \(u\)-to-\(x\) distance plus the \(x\)-to-\(v\) distance. The first BFS finds a shortest path from \(u\) to \(x\) and the second finds a shortest path from \(x\) to \(v\); joining them gives a path achieving this minimum.
Tags: shortest paths
Let \(G\) be an undirected graph, and let \(u, v,\) and \(z\) be three nodes in the graph. Consider the problem of finding a shortest path from \(u\) to \(v\) which passes through node \(z\).
True or False: a shortest path from \(u\) to \(v\) passing through \(z\) may include node \(u\) twice.
True.
Consider the "chain" graph A - B - C - D - E. The shortest path from C to E that passes through B is C - B - C - D - E. It passes through C twice.
Tags: shortest paths
True or False: It is possible for two arbitrary nodes to have a negative shortest path distance between them without the presence of a negative cycle in the graph.
True. For example, if there is a single edge \((u, v)\) with weight \(-1\) and no other edges, the shortest path distance from \(u\) to \(v\) is \(-1\), and there is no cycle at all.
Tags: bellman-ford, dijkstra, shortest paths
Suppose you are planning a trip, and are intending to travel by air from San Diego to another city, with potentially multiple stops in between. You would like to schedule flights that take the least amount of time to get to your destination. In order to do this, you are thinking about these flights as a graph, where each airport is a node, and the weight of an edge connecting two airports corresponds to the amount of time it takes to travel between them.
Which algorithm should you choose to compute the fastest route from San Diego to each of the other cities? If two algorithms both find the fastest routes, pick the one which has a better time complexity.
Dijkstra's Algorithm. The graph is weighted, so BFS and DFS won't find shortest paths. Travel times are never negative, so both Bellman-Ford and Dijkstra's algorithm work, but Dijkstra's algorithm has the better time complexity.
Tags: bellman-ford, dijkstra, shortest paths
Suppose you are planning a trip by air from San Diego to another city, with potentially multiple stops in between. You are thinking about the flights as a graph, where each airport is a node and each flight is an edge. You don't care about the travel time, and instead care about the cost, so the weight of an edge is the cost of that flight. Also suppose that the airline has a special deal, where flights between certain cities will give you frequent flyer miles, or points towards free flights that you can use later in your trip. In other words, some flights have a negative cost. If you want to find the lowest cost route, which algorithm would be the best choice?
Bellman Ford. Some edge weights are negative, and Dijkstra's algorithm is not guaranteed to find shortest paths when there are negative edge weights. Bellman-Ford works with negative weights (as long as there are no negative cycles), and BFS and DFS don't find shortest paths in weighted graphs.
Tags: minimum spanning trees, shortest paths
Suppose there is a unique shortest path \(p\) between nodes \(u\) and \(v\) in a graph \(G\) and that there is a unique minimum spanning tree \(T\) of \(G\). True or false: the path between \(u\) and \(v\) in the MST \(T\) must be the same as the path \(p\).
False. Consider a triangle on nodes \(u\), \(v\), and \(w\) with edge weights \(w(u, v) = 3\), \(w(u, w) = 2\), and \(w(w, v) = 2\). The unique MST uses edges \((u, w)\) and \((w, v)\), so the path from \(u\) to \(v\) in the MST has length 4. But the unique shortest path from \(u\) to \(v\) is the single edge \((u, v)\), with length 3.