1. Often there are multiple shortest paths between two nodes of a graph. Give a linear-time algorithm for the following task.
- Input: A undirected graph G = (V, E) with unit edge lengths; nodes u, v ∈ V.
- Output: The number of distinct shortest paths from u to v.
find_num_paths(Graph): number = 0 For all u in V, and v in V: distance(u) = 0 distance(v) = infinity distance_queue = createQueue(V)
// Store the distance(v) values as key in distance_queue . while (distance_queue.isEmpty() == false) v=deleteMin(distance_queue) // Extract the vertex with minimum key value and set it as v. For all edges (v,i) in E: if (distance(i) == distance(v)+length(v,i) ) number++ return number
/*
should point out using a variable to count the number of paths for each node,
not just using one variable for the whole graph to record the number of paths.
Should point out updating the number of paths variable by summing the number of paths of its parent nodes
*/
2. There’s a natural intuition that two nodes that are far apart in a communication
network—separated by many hops—have a more tenuous
connection than two nodes that are close together. There are a number
of algorithmic results that are based to some extent on different ways of
making this notion precise. Here’s one that involves the susceptibility of
paths to the deletion of nodes.
有一种自然的直觉认为，在通信网络中相距很远的两个节点——被许多跳点隔开——比两个相距很近的节点有更微弱的连接。
有很多算法的结果在某种程度上是基于使这个概念更精确的不同方法。
这是一个涉及到删除节点路径的易感性的问题。
Suppose that an n-node undirected graph G = (V, E) contains two
nodes s and t such that the distance between s and t is strictly greater
than n/2. Show that there must exist some node v, not equal to either s
or t, such that deleting v from G destroys all s-t paths. (In other words,
the graph obtained from G by deleting v contains no path from s to t.)
Give an algorithm with running time O(m + n) to find such a node v.
假设一个n节点无向图G = (V, E)包含两个节点s和t，使得s和t之间的距离严格大于n/2。
证明一定存在某个节点v，既不等于s，也不等于t，这样从G中删除v就会破坏所有的s-t路径。
(换句话说，通过删除v从G得到的图不包含从s到t的路径。)
给出一个运行时间为O(m + n)的算法来寻找这样的节点v。
Proof by contradiction: Assume that if d > n/2, all layers have at least 2 nodes. Let s be in one layer L(n), and t in another layer L(n+d). Between L(n) and L(n+d-1), there are at least 2 nodes in each layer, Thus, there are at least 2(n/2) = n nodes, Before counting for s and t, there are already n nodes in the assumed graph, but G has in total n nodes, so our assumption is false, which means that there must exist one layer with only one single node v. Thus, if we delete v, we are stuck in the layer before v and cannot reach t. Thus, the statement is proved. // Algorithm in pseudocode: find_node_v(Graph, s): create set Set = null create queue Q = null Q.enqueue(s) Num_Nodes = 0 node = null while (Q.isEmpty() == false) { current = Q.dequeue() if (current == t) return for (each node n that is adjacent to current) { Num_Nodes += 1 // count the number of nodes in each layer Node = n if (Set.contains(n) == false ) { Set.add(n) n.parent = current Q.enqueue(n) } } if (Num_Nodes == 1) return node }
3.
You are given a set of cities, along with the pattern of highways between them, in the form of an undirected graph G = (V, E).
Each stretch of highway e ∈ E connects two of the cities, and you know its length in miles, le.
You want to get from city s to city t.
There’s one problem: your car can only hold enough gas to cover L miles. There are gas stations in each city, but not between cities.
给定一组城市，以及它们之间的高速公路模式，以无向图G = (V, E)的形式给出。
e∈E 公路的每一段都连接着两个城市，你知道它的长度是多少英里。
你想从s城到t城。
有一个问题:你的车只能装下足够行驶1英里的油。每个城市都有加油站，但城市之间没有。
Therefore, you can only take a route if every one of its edges has length le ≤ L.
Given the limitation on your car’s fuel tank capacity, show how to determine in linear time whether there is a feasible route from s to t.
因此，你只能选择一条每条边的长度小于L的路径。
G有n个顶点和m条边。G的一条特定边e被指定。
给出一个运行时间为O(m + n)的算法来判断e是否包含在G的最小生成树中。
(1) e必须是切割的最小成本和
(2) e不应是循环的最大值边。
我们设计了一个基于事实1的算法。
假设e = (u, v)，去掉G中代价≥ce的所有边，u和v将不再连通。
算法如下。
步骤2:使用BFS或DFS测试u和v之间的连接性。
如果u和v仍然是连通的，那么e就不是切割过程中唯一的最小代价边。
所以e不属于MST。
否则，e属于MST。