【免费】EfficientAlgorithmsandIntractableProblems

需积分: 0 47 浏览量 2010-03-17 17:10:24 上传评论收藏 306KB PDF 举报

资源详情

资源评论

资源推荐

Chapter 4

Paths in graphs

4.1 Distances

Depth-ﬁrst search readily identiﬁes all the vertices of a graph that can be reached from a

designated starting point. It also ﬁnds explicit paths to these vertices, summarized in its

search tree (Figure 4.1). However, these paths might not be the most economical ones possi-

ble. In the ﬁgure, vertex C is reachable from S by traversing just one edge, while the DFS tree

shows a path of length 3. This chapter is about algorithms for ﬁnding shortest paths in graphs.

Path lengths allow us to talk quantitatively about the extent to which different vertices of

a graph are separated from each other:

The distance between two nodes is the length of the shortest path between them.

To get a concrete feel for this notion, consider a physical realization of a graph that has a ball

for each vertex and a piece of string for each edge. If you lift the ball for vertex s high enough,

the other balls that get pulled up along with it are precisely the vertices reachable from s.

And to ﬁnd their distances from s, you need only measure how far below s they hang.

Figure 4.1 (a) A simple graph and (b) its depth-ﬁrst search tree.

(a)

BD C

(b)

115

116

Algorithms

Figure 4.2 A physical model of a graph.

E S

D C

D E

In Figure 4.2 for example, vertex B is at distance 2 from S, and there are two shortest

paths to it. When S is held up, the strings along each of these paths become taut. On the

other hand, edge (D, E) plays no role in any shortest path and therefore remains slack.

4.2 Breadth-ﬁrst search

In Figure 4.2, the lifting of s partitions the graph into layers: s itself, the nodes at distance

1 from it, the nodes at distance 2 from it, and so on. A convenient way to compute distances

from s to the other vertices is to proceed layer by layer. Once we have picked out the nodes

at distance 0, 1, 2, . . . , d, the ones at d + 1 are easily determined: they are precisely the as-yet-

unseen nodes that are adjacent to the layer at distance d. This suggests an iterative algorithm

in which two layers are active at any given time: some layer d, which has been fully identiﬁed,

and d + 1, which is being discovered by scanning the neighbors of layer d.

Breadth-ﬁrst search (BFS) directly implements this simple reasoning (Figure 4.3). Ini-

tially the queue Q consists only of s, the one node at distance 0. And for each subsequent

distance d = 1, 2, 3, . . ., there is a point in time at which Q contains all the nodes at distance

d and nothing else. As these nodes are processed (ejected off the front of the queue), their

as-yet-unseen neighbors are injected into the end of the queue.

Let’s try out this algorithm on our earlier example (Figure 4.1) to conﬁrm that it does the

right thing. If S is the starting point and the nodes are ordered alphabetically, they get visited

in the sequence shown in Figure 4.4. The breadth-ﬁrst search tree, on the right, contains the

edges through which each node is initially discovered. Unlike the DFS tree we saw earlier, it

has the property that all its paths from S are the shortest possible. It is therefore a shortest-

path tree.

Correctness and efﬁciency

We have developed the basic intuition behind breadth-ﬁrst search. In order to check that

the algorithm works correctly, we need to make sure that it faithfully executes this intuition.

What we expect, precisely, is that

For each d = 0, 1, 2, . . ., there is a moment at which (1) all nodes at distance ≤ d

S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani

117

Figure 4.3 Breadth-ﬁrst search.

procedure bfs(G, s)

Input: Graph G = (V, E), directed or undirected; vertex s ∈ V

Output: For all vertices u reachable from s, dist(u) is set

to the distance from s to u.

for all u ∈ V :

dist(u) = ∞

dist(s) = 0

Q = [s] (queue containing just s)

while Q is not empty:

u = eject(Q)

for all edges (u, v) ∈ E:

if dist(v) = ∞:

inject(Q, v)

dist(v) = dist(u) + 1

from s have their distances correctly set; (2) all other nodes have their distances

set to ∞; and (3) the queue contains exactly the nodes at distance d.

This has been phrased with an inductive argument in mind. We have already discussed both

the base case and the inductive step. Can you ﬁll in the details?

The overall running time of this algorithm is linear, O(|V | + |E|), for exactly the same

reasons as depth-ﬁrst search. Each vertex is put on the queue exactly once, when it is ﬁrst en-

countered, so there are 2 |V | queue operations. The rest of the work is done in the algorithm’s

innermost loop. Over the course of execution, this loop looks at each edge once (in directed

graphs) or twice (in undirected graphs), and therefore takes O(|E|) time.

Now that we have both BFS and DFS before us: how do their exploration styles compare?

Depth-ﬁrst search makes deep incursions into a graph, retreating only when it runs out of new

nodes to visit. This strategy gives it the wonderful, subtle, and extremely useful properties

we saw in the Chapter 3. But it also means that DFS can end up taking a long and convoluted

route to a vertex that is actually very close by, as in Figure 4.1. Breadth-ﬁrst search makes

sure to visit vertices in increasing order of their distance from the starting point. This is a

broader, shallower search, rather like the propagation of a wave upon water. And it is achieved

using almost exactly the same code as DFS—but with a queue in place of a stack.

Also notice one stylistic difference from DFS: since we are only interested in distances

from s, we do not restart the search in other connected components. Nodes not reachable from

s are simply ignored.

S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani

119

Figure 4.6 Breaking edges into unit-length pieces.

C E

4.4 Dijkstra’s algorithm

4.4.1 An adaptation of breadth-ﬁrst search

Breadth-ﬁrst search ﬁnds shortest paths in any graph whose edges have unit length. Can we

adapt it to a more general graph G = (V, E) whose edge lengths l

are positive integers?

A more convenient graph

Here is a simple trick for converting G into something BFS can handle: break G’s long edges

into unit-length pieces, by introducing “dummy” nodes. Figure 4.6 shows an example of this

transformation. To construct the new graph G

For any edge e = (u, v) of E, replace it by l

edges of length 1, by adding l

− 1

dummy nodes between u and v.

Graph G

contains all the vertices V that interest us, and the distances between them are

exactly the same as in G. Most importantly, the edges of G

all have unit length. Therefore,

we can compute distances in G by running BFS on G

Alarm clocks

If efﬁciency were not an issue, we could stop here. But when G has very long edges, the G

it engenders is thickly populated with dummy nodes, and the BFS spends most of its time

diligently computing distances to these nodes that we don’t care about at all.

To see this more concretely, consider the graphs G and G

of Figure 4.7, and imagine that

the BFS, started at node s of G

, advances by one unit of distance per minute. For the ﬁrst

99 minutes it tediously progresses along S − A and S − B, an endless desert of dummy nodes.

Is there some way we can snooze through these boring phases and have an alarm wake us

up whenever something interesting is happening—speciﬁcally, whenever one of the real nodes

(from the original graph G) is reached?

We do this by setting two alarms at the outset, one for node A, set to go off at time T = 100,

and one for B, at time T = 200. These are estimated times of arrival, based upon the edges

currently being traversed. We doze off and awake at T = 100 to ﬁnd A has been discovered. At

剩余23页未读，继续阅读

评论收藏

内容反馈

luckyfancy

粉丝: 0
资源: 15

Efficient Algorithms and Intractable Problems_ch4

评论0

最新资源

Efficient Algorithms and Intractable Problems_ch4

评论0

Efficient Algorithms and Intractable Problems_ch7

Efficient Algorithms and Intractable Problems_ch8

Efficient Algorithms and Intractable Problems_ch6

Efficient Algorithms and Intractable Problems_ch5

Efficient Algorithms and Intractable Problems_ch2

Efficient Algorithms and Intractable Problems_ch3

Tarjan-data_structures_and_network_algorithms.pdf

Dictionary_of_Algorithms_Data_Structures_and_Problems

Wai-Ki_Ching_markov_chains_models_algorithms_and_applications_second_edition

[Wordware]Memory_Management-Algorithms_And_Implementation_In_C_C++.zip

data_structures_and_algorithms_in_java_4th_edition.4630586266.pdf

data_structures_and_algorithms_in_java_4th_edition.4630586266.rar

recommendation-algorithms-master_recommendation_algorithms_推荐系统_

Algorithms_Illuminated_Part_2_Graph_Algorithms_and_Data_Structures

Algorithms-_Data_Structures-_and_Problem_Solving__algorithms

Sams_Teach_Yourself_Data_Structures_and_Algorithms_in_24_Hours

[AddisonWesley]Algorithms_Data_Structures_And_Problem_Solving_With_C++.zip

Qt 5实现串口调试助手 （源工程文件、0积分下载）

【SystemVerilog】路科验证V2学习笔记（全600页）.pdf

AutoSAR标准协议4.2.2

光伏-储能并网系统仿真.rar

GD32替换STM32注意事项.pdf

NPPJSONViewer.zip

XCP协议的规范文档

VS2015安装证书，JavaScript_ProjectSystem.msi，JavaScript_LanguageService.msi

CANoe通过CAPL脚本实现自动测试

蓝牙BLE协议中文版.pdf

BaiduOCR.zip

最新资源

Qt 5实现串口调试助手（源工程文件、0积分下载）