Bài giảng Toán rời rạc - Bài 18: Đường đi trên đồ thị - Trần Vĩnh Đức

hese vertices, sum- marized in its search tree (Figure 4.1). However, these paths might not be the most economical ones possible. In the figure, 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 finding 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 find their distances from s, you need only measure how far below s they hang. In Figure 4.2, for example, vertex B is at distance 2 from S, and there are two shortest paths to it. Whe S is held up, the strings along each of these paths become taut. Figure 4.1 (a) A simple graph and (b) its depth-first search tree. (a) E AS BD C (b) S A B D E C 104 P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 Chapter 4 Paths in graphs 4.1 Distances Depth-first search readily identifies all the vertices of a graph that can be reached from a designated starting point. It also finds explicit paths to these vertices, sum- marized in its search tree (Figure 4.1). However, these paths might not be the most economical ones possible. In the figure, 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 finding 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 f a graph hat 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 ar precisely the vertices reachable from s. And to find their distances from s, you need only measure how far below s they hang. 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. Figure 4.1 (a) A simple graph and (b) its depth-first search tree. (a) E AS BD C (b) S A B D E C 104 Đường đi trên cây DFS thường không phải là đường đi ngắn nhất. 4 / 52 Khoảng cách Khoảng cách giữa hai đỉnh là độ dài của đường đi ngắn nhất giữa chúng. P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 Chapter 4 Paths in graphs 4.1 Distances Depth-first search readily identifies all the vertices of a graph that can be reached from a designated starting point. It also finds explicit paths to these vertices, sum- marized in its search tree (Figure 4.1). However, these paths might not be the most economical ones possible. In the figure, 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 finding 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 find their distances from s, you need only measure how far below s they hang. 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. Figure 4.1 (a) A simple graph and (b) its depth-first search tree. (a) E AS BD C (b) S A B D E C 104 v Khoảng cách (S− v) A B C D E 5 / 52 Mô hình vật lý của đồ thị Giả sử rằng mọi cạnh có cùng độ dài. Ta nhấc đỉnh S lên: P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 Chapter 4 Algorithms 105 Figure 4.2 A physical model of a graph. B E S D C A D EC B A S On the other hand, edge (D, E ) plays no role in any shortest path and therefore remains slack. 4.2 Breadth-first 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 identified, and d + 1, which is being discovered by scanning the neighbors of layer d. Breadth-first search (BFS) directly implements this simple reasoning (Figure 4.3). Initially 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 confirm 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-first 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 efficiency We have developed the basic intuition behind breadth-first 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 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. P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 Chapter 4 Algorithms 105 Figure 4.2 A physical model of a graph. B E S D C A D EC B A S On the other hand, edge (D, E ) plays no role in any shortest path and therefore remains slack. 4.2 Breadth-first search In Figure 4.2, the lifting of s partitions th graph into laye s: s itself, the odes at distance 1 from it, the nodes at di tance 2 from it, and so on. A convenient way to compute distances from s to the other v rtices is to proceed layer by layer. Once we have picked out the nodes at distan e 0, 1, 2, . . . , d, th ones at d + 1 are easily determined: they are pre isely t e as-yet-unseen nod s that are adjacent to the layer at distance d. This suggests an iterative algorit m in which two layers are active at any given time: some layer d, which has been fully identified, and d + 1, which is being discovered by scanning the neighbors of layer d. Breadth-first search (BFS) directly implements this simple reasoning (Figure 4.3). Initially 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 confirm 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-first search tree, on the right, contains the edges through which eac 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 effici ncy We have developed the basic intuition behind breadth-fir t 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 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. 6 / 52 Tìm kiếm theo chiều rộng (Breadth-First Search) Chia đồ thị thành các mức: ▶ S là mức có khoảng cách 0. ▶ Các đỉnh có khoảng cách tới S bằng 1. ▶ Các đỉnh có khoảng cách tới S bằng 2 ▶ ... P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 Chapter 4 Algorithms 105 Figure 4.2 A physical model of a graph. B E S D C A D EC B A S On the other hand, edge (D, E ) plays no role in any shortest path and therefore remains slack. 4.2 Breadth-first 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 identified, and d + 1, which is being discovered by scanning the neighbors of layer d. Breadth-first search (BFS) directly implements this simple reasoning (Figure 4.3). Initially 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 confirm 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-first 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 efficiency We have developed the basic intuition behind breadth-first 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 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. Ý tưởng thuật toán: Khi mức d đã được xác định, mức d+ 1 có thể thăm bằng cách duyệt qua các hàng xóm của mức d. 7 / 52 Ý tưởng loang theo chiều rộng Khởi tạo: Hàng đợi Q chỉ chứa đỉnh s, là đỉnh duy nhất ở mức 0. Với mỗi khoảng cách d = 1, 2, 3, . . . , ▶ sẽ có thời điểm Q chỉ chứa các đỉnh có khoảng cách d và không có gì khác. ▶ Khi đó các đỉnh có khoảng cách d này sẽ được loại bỏ dần từ đầu hàng đợi, ▶ và các hàng xóm chưa được thăm sẽ được thêm vào cuối hàng đợi. 8 / 52 Bài tập Chạy thuật toán BFS cho đồ thị dưới đây bắt đầu từ đỉnh S. Ghi ra hàng đợi Q sau mỗi lần thăm đỉnh. P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 Chapter 4 Paths in graphs 4.1 Distances Depth-first search readily identifies all the vertices of a graph that can be reached from a designated starting point. It also finds explicit paths to these vertices, sum- marized in its search tree (Figure 4.1). However, these paths might not be the most economical ones possible. In the figure, 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 finding 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 find their distances from s, you need only measure how far below s they hang. 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. Figure 4.1 (a) A simple graph and (b) its depth-first search tree. (a) E AS BD C (b) S A B D E C 104 Đỉnh thăm Hàng đợi S [S] 9 / 52 procedure bfs(G, s) Input: đồ thị G = (V,E), có hướng hoặc vô hướng; một đỉnh s ∈ V Output: Với mỗi đỉnh u đến được từ s, dist(u) = khoảng cách từ s tới u. for all u ∈ V: dist(u) = ∞ dist(s) = 0 Q = [s] (hàng đợi chỉ chứa s) while Q khác rỗng: u = eject(Q) (loại bỏ u khỏi hàng đợi) for all edges (u, v) ∈ E: if dist(v) = ∞: inject(Q, v) (thêm v vào hàng đợi) dist(v) = dist(u) + 1 10 / 52 Bài tập Hãy chạy thuật toán BFS cho đồ thị dưới đây và ghi ra nội dung của hàng đợi Q sau mỗi bước: P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 Chapter 4 Paths in graphs 4.1 Distances Depth-first search readily identifies all the vertices of a graph that can be reached from a designated starting point. It also finds explicit paths to these vertices, sum- marized in its search tree (Figure 4.1). However, these paths might not be the most economical ones possible. In the figure, 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 finding 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 find their distances from s, you need only measure how far below s they hang. 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. Figure 4.1 (a) A simple graph and (b) its depth-first search tree. (a) E AS BD C (b) S A B D E C 104 Thứ tự thăm đỉnh Hàng đợi S [S] 11 / 52 Nội dung Khoảng cách và tìm kiếm theo chiều rộng Thuật toán Dijkstra Cài đặt hàng đợi ưu tiên Đường đi ngắn nhất khi có cạnh độ dài âm Đường đi ngắn nhất trong một DAG Độ dài của cạnh P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 Chapter 4 Algorithms 107 and extremely useful properties we saw in 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-first search makes sure to visit vertices in in- creasing order of their distance from the starting point. This is a broader, shal- lower 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 dis- tances from s, we do not restart the search in other connected components. Nodes not reachable from s are simply ignored. 4.3 Lengths on edges Breadth-first search treats all edges as having the same length. This is rarely true in applications where shortest paths are to be found. For instance, suppose you are driving from San Francisco to Las Vegas, and want to find the quickest route. Figure 4.5 shows the major highways you might conceivably use. Picking the right combination of them is a shortest-path problem in which the length of each edge (each stretch of highway) is important. For the remainder of this chapter, we will deal with this more general scenario, annotating every edge e ∈ E with a length le. If e = (u, v), we will sometimes also write l(u, v) or luv. Figure 4.5 Edge lengths often matter. Francisco San Los Angeles Bakersfield Sacramento Reno Las Vegas 409 290 95 271 133 445 291 112 275 These le’s do not have to correspond to physical lengths. They could denote time (driving time between cities) or money (cost of taking a bus), or any other quantity that we would like to conserve. In fact, there are cases in which we need to use negative lengths, but we will briefly overlook this particular complication. Trong các bài toán thực tế, mỗi cạnh e thường gắn với độ dài le. 13 / 52 Câu hỏi Liệu ta có thể sửa thuật toán BFS để nó chạy được trên đồ thị tổng quát G = (V,E) trong đó mỗi cạnh có độ dài nguyên dương le? 14 / 52 Tách cạnh thành các cạnh với độ dài đơn vị P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 108 4.4 Dijkstra’s algorithm 4.4 Dijkstra’s algorithm 4.4.1 An adaptation of breadth-first search Breadth-first search finds 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 le 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 le edges of length 1, by adding le − 1 dummy nodes between u and v. Grap 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 ′. Figure 4.6 Breaking edges into unit-length pieces. C A B E D C E DB A1 2 2 4 23 1 Alarm clocks If efficiency 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 first 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— specifically, 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 find A has been discovered. At this point, the estimated time of arrival for B is adjusted to T = 150 and we change its alarm accordingly. P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 108 4.4 Dijkstra’s algorithm 4.4 Dijkstra’s algorithm 4.4.1 An adaptation of breadth-first sea ch Bread h-first s arch finds 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 le 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 le edges of length 1, by adding le − 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 ′. Figure 4.6 Breaking edges into unit-length pieces. C A B E D C E DB A1 2 2 4 23 1 Alarm clocks If efficien y 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 first 99 minutes it tediously progresses along S − A and S − B, an endless desert of dummy node . Is there som way we can s ooze through these boring phases and have an alarm wake us up whenever somethi interesti g is happening— specifically, 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 o 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 find A has been discovered. At this point, the estimated time of arrival for B is adjusted to T = 150 and we change its alarm accordingly. Thay cạnh e = (u, v) bởi le cạnh độ dài 1, bằng cách thêm le − 1 đỉnh tạm giữa u và v. 15 / 52 Vấn đề P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 Chapter 4 Algorithms 109 Figure 4.7 BFS on G ′ is mostly uneventful. The dotted lines show some early “wavefronts.” G: A B S 200 100 50 G : S A B More generally, at any given moment the breadth-first search is advancing along certain edges of G , and there is an alarm for every endpoint node toward which it is moving, set to go off at the estimated time of arrival at that node. Some of these might be overestimates because BFS may later find shortcuts, as a result of future arrivals elsewhere. In the preceding example, a quicker route to B was revealed upon arrival at A. However, nothing interesting can possibly happen before an alarm goes off. The sounding of the next alarmmust therefore signal the arrival of the wavefront to a real node u ∈ V by BFS. At that point, BFS might also start advancing along some new edges out of u, and alarms need to be set for their endpoints. The following “alarm clock algorithm” faithfully simulates the execution of BFS on G ′. ! Set an alarm clock for node s at time 0.! Repeat until there are no more alarms: Say the next alarm goes off at time T , for node u. Then: – The distance from s to u is T . – For each neighbor v of u in G : ∗ If there is no alarm yet for v, set one for time T + l(u, v). ∗ If v’s alarm is set for later than T + l(u, v), then reset it to this earlier time. Dijkstra’s algorithm The alarm clock algorithm computes distances in any graph with positive integral edge lengths. It is almost ready for use, except that we need to somehow implement the system of alarms. The right data structure for this job is a priority queue (usually implemented via a heap), which maintains a set of elements (nodes) with associated numeric key values (alarm times) and supports the following operations: Insert. Add a new element to the set. Decrease-key. Accommodate the decrease in key value of a particular element.1 1The name decrease-key is standard but is a little misleading: the priority queue typically does not itself change key values. What this procedure really does is to notify the queue that a certain key value has been decreased. P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 Chapter 4 Algorithms 109 Figure 4.7 BFS on G ′ is mostly uneventful. The dotted lines show some early “wavefronts.” G: A B S 200 100 50 G : S A B More generally, at any given moment the breadth-first search is advancing along certain edges of G , and there is an alarm for every endpoint node toward which it is moving, set to go off at the estimated time of arrival at that node. Some of these might be overestimates because BFS may ter find shortcuts, as a resul of future arrivals elsewhere. In the preceding example, a quicker route to B was revealed upon arrival at A. However, nothing interesting can possibly happen before an alarm goes off. The sounding of the next alarmmust therefore signal the arrival of the wavefront to a r al node u ∈ V by BFS. At that point, BFS might also sta t advancing along some new edges out of u, and alarms need to be set for their endpoints. e following “alarm clock algorithm” faithfully simulates the execution of BFS on G ′. ! Set an alarm clock for node s at ti e 0.! Repeat until there are no more alarms: Say the next alarm goes off at time T , for node u. Then: – The distance from s to u is T . – For e ch neighbor v of u in G : ∗ If there is no alarm yet for v, set one for time T + l(u, v). ∗ If v’s alarm is set for later than T + l(u, v), then reset it to this earlier time. Dijkstra’s algorithm The alarm clock algorithm computes distances in any graph with positive integral edge lengths. It is almost ready for use, except that we need to somehow implement the system of alarms. The right data structure for this job is a priority queue (usually implemented via a heap), which maintains a set of elements (nodes) with associated numeric key values (alarm times) and supports the following opera ions: Insert. Add a new element to the set. Decrease-key. Accommodate the decrease in key value of a particular element.1 1The name decrease-key is standard but is a little misleading: the priority queue typically does not itself change key values. What this procedure really does is to notify the queue that a certain key value has been decreased. Cả 99 bước di chuyển đầu tiên đều xử lý S−A và S− B trên các đỉnh tạm. 16 / 52 Giải pháp: Đặt Alarm clock! ▶ Với đỉnh A, đặt hẹn T = 100 ▶ Với đỉnh B, đặt hẹn T = 200 ▶ Bị đánh thức khi A được thăm lúc T = 100 ▶ Ước lượng lại thời gian đến của B là T = 150; và đặt lại Alarm cho B. P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 Chapter 4 Algorithms 109 Figure 4.7 BFS on G ′ is mostly uneventful. The dotted lines show some early “wavefronts.” G: A B S 200 100 50 G : S A B More generally, at any given moment the breadth-first search is advancing along certain edges of G , and there is an alarm for every endpoint node toward which it is moving, set to go off at the estimated time of arrival at that node. Some of these might be overestimates because BFS may later find shortcuts, as a result of future arrivals elsewhere. In the preceding example, a quicker route to B was revealed upon arrival at A. However, nothing interesting can possibly happen before an alarm goes off. The sounding of the next alarmmust therefore signal the arrival of the wavefront to a real node u ∈ V by BFS. At that point, BFS might also start advancing along some new edges out of u, and alarms need to be set for their endpoints. The following “alarm clock algorithm” faithfully simulates the execution of BFS on G ′. ! Set an alarm clock for node s at time 0.! Repeat until there are no more alarms: Say the next alarm goes off at time T , for node u. Then: – The distance from s to u is T . – For each neighbor v of u in G : ∗ If there is no alarm yet for v, set one for time T + l(u, v). ∗ If v’s alarm is set for later than T + l(u, v), then reset it to this earlier time. Dijkstra’s algorithm The alarm clock algorithm computes distances in any graph with positive integral edge lengths. It is almost ready for use, except that we need to somehow implement the system of alarms. The right data structure for this job is a priority queue (usually implemented via a heap), which maintains a set of elements (nodes) with associated numeric key values (alarm times) and supports the following operations: Insert. Add a new element to the set. Decrease-key. Accommodate the decrease in key value of a particular element.1 1The name decrease-key is standard but is a little misleading: the priority queue typically does not itself change key values. What this procedure really does is to notify the queue that a certain key value has been decreased. 17 / 52 Thuật toán Alarm Clock Đặt một alarm clock cho đỉnh s tại thời điểm T = 0 Lặp lại cho đến khi không còn alarm: Giả sử alarm kêu tại thời điểm T cho đỉnh u. Vậy thì: - Khoảng cách từ s tới u là T. - Với mỗi hàng xóm v của u trong G: * Nếu vẫn chưa có alarm cho v, đặt alarm cho v tại thời điểm T+ l(u, v). * Nếu alarm của v đã đặt, nhưng lại muộn hơn so với T+ l(u, v), vậy thì đặt lại alarm cho v bằng T+ l(u, v). 18 / 52 Ví dụ P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 108 4.4 Dijkstra’s algorithm 4.4 Dijkstra’s algorithm 4.4.1 An adaptation of breadth-first search Breadth-first search finds 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 le 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 le edges of length 1, by adding le − 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 ′. Figure 4.6 Breaking edges into unit-length pieces. C A B E D C E DB A1 2 2 4 23 1 Alarm clocks If efficiency 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 first 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— specifically, 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 find A has been discovered. At this point, the estimated time of arrival for B is adjusted to T = 150 and we change its alarm accordingly. Thời gian A B C D E 0 − − − − 0 0 2 1 − − 1 2 1 − 5 2 2 4 5 4 4 5 5 5 0 2 1 4 4 19 / 52 Hàng đợi ưu tiên Tại sao cần hàng đợi ưu tiên? Để cài đặt hệ thống Alarm. Hàng đợi ưu tiên là gì? Là một tập với mỗi phần tử được gắn với giá trị số (còn gọi là khóa) và có các phép toán sau: Insert. Thêm một phần tử mới vào tập. Decrease-key. Giảm giá trị khóa của một phần tử cụ thể. Delete-min. Trả lại phần tử có khóa nhỏ nhất và xóa nó khỏi tập. Make-queue. xây dựng hàng đợi ưu tiên cho tập phần tử và giá trị khóa cho trước. Khóa của mỗi phần tử (đỉnh) ở đây chính là alarm của đỉnh đó. Insert và Descrease-key để đặt alarm; Delete-min để xác định thời điểm alarm tiếp theo kêu. 20 / 52 procedure dijkstra(G, l, s) Input: đồ thị G = (V,E), có hướng hoặc vô hướng; độ dài các cạnh {le : e ∈ E}; đỉnh s ∈ V Output: Với mỗi đỉnh u đến được từ s, dist(u) = khoảng cách từ s tới u. for all u ∈ V: dist(u) = ∞ prev(u) = nil (đỉnh trước u trong đường đi ngắn nhất) dist(s) = 0 H = makequeue(V) (dùng các giá trị dist làm khóa) while H khác rỗng: u = deletemin(H) for all edges (u, v) ∈ E: if dist(v) > dist(u) + l(u, v): dist(v) = dist(u) + l(u, v) prev(v) = u (đỉnh trước v là u) decreasekey(H, v) 21 / 52 Ví dụ Hãy chạy thuật toán Dijkstra trên đồ thị sau. Sau mỗi bước, hãy chỉ ra mảng prev, phần tử và khóa của hàng đợi ưu tiên. P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 Chapter 4 Algorithms 111 Figure 4.9 A complete run of Dijkstra’s algorithm, with node A as the starting point. Also s own are the ssociated dist values and the final shortest-path tree. B C D E A 4 1 3 2 4 1 3 5 2 A: 0 D:∞ B: 4 E:∞ C: 2 B C D E A 4 2 4 1 3 5 2 1 3 A: 0 D: 6 B: 3 E: 7 C: 2 B C D E A 4 1 3 2 4 1 3 5 2 A: 0 D: 5 B: 3 E: 6 C: 2 B C D E A 4 1 3 2 1 5 2 3 4 A: 0 D: 5 B: 3 E: 6 C: 2 B C D E A 2 1 3 2 22 / 52 Ví dụ: Bước 1 P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 Chapter 4 Algorithms 111 Figure 4.9 A complete run of Dijkstra’s algorithm, with node A as the starting point. Also shown are the associated dist values and the final shortest-path tree. B C D E A 4 1 3 2 4 1 3 5 2 A: 0 D:∞ B: 4 E:∞ C: 2 B C D E A 4 2 4 1 3 5 2 1 3 A: 0 D: 6 B: 3 E: 7 C: 2 B C D E A 4 1 3 2 4 1 3 5 2 A: 0 D: 5 B: 3 E: 6 C: 2 B C D E A 4 1 3 2 1 5 2 3 4 A: 0 D: 5 B: 3 E: 6 C: 2 B C D E A 2 1 3 2 23 / 52 Ví dụ: Bước 2 P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 Chapter 4 Algorithms 111 Figure 4.9 A complete run of Dijkstra’s algorithm, with node A as the starting point. Also shown are the associated dist values and the final shortest-path tree. B C D E A 4 1 3 2 4 1 3 5 2 A: 0 D:∞ B: 4 E:∞ C: 2 B C D E A 4 2 4 1 3 5 2 1 3 A: 0 D: 6 B: 3 E: 7 C: 2 B C D E A 4 1 3 2 4 1 3 5 2 A: 0 D: 5 B: 3 E: 6 C: 2 B C D E A 4 1 3 2 1 5 2 3 4 A: 0 D: 5 B: 3 E: 6 C: 2 B C D E A 2 1 3 2 24 / 52 Ví dụ: Bước 3 P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 Chapter 4 Algorithms 111 Figure 4.9 A complete run of Dijkstra’s algorithm, with node A as the starting point. Also shown are the associated dist values and the final shortest-path tree. B C D E A 4 1 3 2 4 1 3 5 2 A: 0 D:∞ B: 4 E:∞ C: 2 B C D E A 4 2 4 1 3 5 2 1 3 A: 0 D: 6 B: 3 E: 7 C: 2 B C D E A 4 1 3 2 4 1 3 5 2 A: 0 D: 5 B: 3 E: 6 C: 2 B C D E A 4 1 3 2 1 5 2 3 4 A: 0 D: 5 B: 3 E: 6 C: 2 B C D E A 2 1 3 2 25 / 52 Ví dụ: Bước 4 P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 Chapter 4 Algorithms 111 Figure 4.9 A complete run of Dijkstra’s algorithm, with node A as the starting point. Also shown are the associated dist values and the final shortest-path tree. B C D E A 4 1 3 2 4 1 3 5 2 A: 0 D:∞ B: 4 E:∞ C: 2 B C D E A 4 2 4 1 3 5 2 1 3 A: 0 D: 6 B: 3 E: 7 C: 2 B C D E A 4 1 3 2 4 1 3 5 2 A: 0 D: 5 B: 3 E: 6 C: 2 B C D E A 4 1 3 2 1 5 2 3 4 A: 0 D: 5 B: 3 E: 6 C: 2 B C D E A 2 1 3 2 26 / 52 Ví dụ: Mảng prev P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 Chapter 4 Algorithms 111 Figure 4.9 A complete run of Dijkstra’s algorithm, with node A as the starting point. Also shown are the associated dist values and the final shortest-path tree. B C D E A 4 1 3 2 4 1 3 5 2 A: 0 D:∞ B: 4 E:∞ C: 2 B C D E A 4 2 4 1 3 5 2 1 3 A: 0 D: 6 B: 3 E: 7 C: 2 B C D E A 4 1 3 2 4 1 3 5 2 A: 0 D: 5 B: 3 E: 6 C: 2 B C D E A 4 1 3 2 1 5 2 3 4 A: 0 D: 5 B: 3 E: 6 C: 2 B C D E A 2 1 3 2 u prev[u] A nil B C C A D B E B 27 / 52 Nội dung Khoảng cách và tìm kiếm theo chiều rộng Thuật toán Dijkstra Cài đặt hàng đợi ưu tiên Đường đi ngắn nhất khi có cạnh độ dài âm Đường đi ngắn nhất trong một DAG Cài đặt hàng đợi ưu tiên dùng mảng ▶ Dùng mảng lưu trữ giá trị khóa cho mỗi phần tử (đỉnh của đồ thị). ▶ Phép toán insert và decreasekey chạy trong O(1). ▶ nhưng deletemin chạy trong O(|V|)! ▶ Với cách cài đặt này, thuật toán Dijkstra chạy trong O(|V|2) 29 / 52 Dùng Binary Heap ▶ Các phần tử được lưu trong cây nhị phân đầy đủ: Mỗi mức trên cây phải được điền đầy từ trái qua phải và phải đầy trước khi thêm mức tiếp theo. ▶ Ràng buộc: Giá trị khóa của nút trên cây phải nhỏ hơn hoặc bằng giá trị khóa của các con. ▶ Các phép toán insert, decreasekey, và deletemin chạy trong O(log |V|) 30 / 52 Ví dụ: Thêm phần tử với khóa 7 vào binary heap P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 116 4.6 Shortest paths in the presence of negative edges Figure 4.11 (a) A binary heap with 10 elements. Only the key values are shown. (b)–(d) The intermediate “bubble-up” steps in inserting an element with key 7. (e)–(g) The “sift-down” steps in a delete-min operation. (a) 3 510 1211 6 8 15 20 13 (b) 3 510 1211 6 8 15 20 13 7 (c) 3 510 11 6 8 15 20 13 12 7 (d) 3 5 11 6 8 15 20 13 12 7 10 (e) 5 11 6 8 15 20 13 12 7 10 (f) 5 11 6 8 15 20 13 7 10 12 (g) 11 8 15 20 13 7 10 6 5 12 (h) 11 8 15 20 13 7 10 5 6 12 31 / 52 P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 116 4.6 Shortest paths in the presence of negative edges Figure 4.11 (a) A binary heap with 10 elements. Only the key values are shown. (b)–(d) The intermediate “bubble-up” steps in inserting an element with key 7. (e)–(g) The “sift-down” steps in a delete-min operation. (a) 3 510 1211 6 8 15 20 13 (b) 3 510 1211 6 8 15 20 13 7 (c) 3 510 11 6 8 15 20 13 12 7 (d) 3 5 11 6 8 15 20 13 12 7 10 (e) 5 11 6 8 15 20 13 12 7 10 (f) 5 11 6 8 15 20 13 7 10 12 (g) 11 8 15 20 13 7 10 6 5 12 (h) 11 8 15 20 13 7 10 5 6 12 32 / 52 P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 116 4.6 Shortest paths in the presence of negative edges Figure 4.11 (a) A binary heap with 10 elements. Only the key values are shown. (b)–(d) The intermediate “bubble-up” steps in inserting an element with key 7. (e)–(g) The “sift-down” steps in a delete-min operation. (a) 3 510 1211 6 8 15 20 13 (b) 3 510 1211 6 8 15 20 13 7 (c) 3 510 11 6 8 15 20 13 12 7 (d) 3 5 11 6 8 15 20 13 12 7 10 (e) 5 11 6 8 15 20 13 12 7 10 (f) 5 11 6 8 15 20 13 7 10 12 (g) 11 8 15 20 13 7 10 6 5 12 (h) 11 8 15 20 13 7 10 5 6 12 33 / 52 P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 116 4.6 Shortest paths in the presence of negative edges Figure 4.11 (a) A binary heap with 10 elements. Only the key values are shown. (b)–(d) The intermediate “bubble-up” steps in inserting an element with key 7. (e)–(g) The “sift-down” steps in a delete-min operation. (a) 3 510 1211 6 8 15 20 13 (b) 3 510 1211 6 8 15 20 13 7 (c) 3 510 11 6 8 15 20 13 12 7 (d) 3 5 11 6 8 15 20 13 12 7 10 (e) 5 11 6 8 15 20 13 12 7 10 (f) 5 11 6 8 15 20 13 7 10 12 (g) 11 8 15 20 13 7 10 6 5 12 (h) 11 8 15 20 13 7 10 5 6 12 34 / 52 Ví dụ: Xóa phần tử ở gốc (deletemin) P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 116 4.6 Shortest paths in the presence of negative edges Figure 4.11 (a) A binary heap with 10 elements. Only the key values are shown. (b)–(d) The intermediate “bubble-up” steps in inserting an element with key 7. (e)–(g) The “sift-down” steps in a delete-min operation. (a) 3 510 1211 6 8 15 20 13 (b) 3 510 1211 6 8 15 20 13 7 (c) 3 510 11 6 8 15 20 13 12 7 (d) 3 5 11 6 8 15 20 13 12 7 10 (e) 5 11 6 8 15 20 13 12 7 10 (f) 5 11 6 8 15 20 13 7 10 12 (g) 11 8 15 20 13 7 10 6 5 12 (h) 11 8 15 20 13 7 10 5 6 12 35 / 52 P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 116 4.6 Shortest paths in the presence of negative edges Figure 4.11 (a) A binary heap with 10 elements. Only the key values are shown. (b)–(d) The intermediate “bubble-up” steps in inserting an element with key 7. (e)–(g) The “sift-down” steps in a delete-min operation. (a) 3 510 1211 6 8 15 20 13 (b) 3 510 1211 6 8 15 20 13 7 (c) 3 510 11 6 8 15 20 13 12 7 (d) 3 5 11 6 8 15 20 13 12 7 10 (e) 5 11 6 8 15 20 13 12 7 10 (f) 5 11 6 8 15 20 13 7 10 12 (g) 11 8 15 20 13 7 10 6 5 12 (h) 11 8 15 20 13 7 10 5 6 12 36 / 52 P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 116 4.6 Shortest paths in the presence of negative edges Figure 4.11 (a) A binary heap with 10 elements. Only the key values are shown. (b)–(d) The intermediate “bubble-up” steps in inserting an element with key 7. (e)–(g) The “sift-down” steps in a delete-min operation. (a) 3 510 1211 6 8 15 20 13 (b) 3 510 1211 6 8 15 20 13 7 (c) 3 510 11 6 8 15 20 13 12 7 (d) 3 5 11 6 8 15 20 13 12 7 10 (e) 5 11 6 8 15 20 13 12 7 10 (f) 5 11 6 8 15 20 13 7 10 12 (g) 11 8 15 20 13 7 10 6 5 12 (h) 11 8 15 20 13 7 10 5 6 12 37 / 52 P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 116 4.6 Shortest paths in the presence of negative edges Figure 4.11 (a) A binary heap with 10 elements. Only the key values are shown. (b)–(d) The intermediate “bubble-up” steps in inserting an element with key 7. (e)–(g) The “sift-down” steps in a delete-min operation. (a) 3 510 1211 6 8 15 20 13 (b) 3 510 1211 6 8 15 20 13 7 (c) 3 510 11 6 8 15 20 13 12 7 (d) 3 5 11 6 8 15 20 13 12 7 10 (e) 5 11 6 8 15 20 13 12 7 10 (f) 5 11 6 8 15 20 13 7 10 12 (g) 11 8 15 20 13 7 10 6 5 12 (h) 11 8 15 20 13 7 10 5 6 12 38 / 52 Nội dung Khoảng cách và tìm kiếm theo chiều rộng Thuật toán Dijkstra Cài đặt hàng đợi ưu tiên Đường đi ngắn nhất khi có cạnh độ dài âm Đường đi ngắn nhất trong một DAG Câu hỏi Liệu ta đã quyết định được đường đi ngắn nhất từ S đến A bằng bao nhiêu chưa? S A B 3 4 ?−2 40 / 52 Giải pháp s u v dist[u] dist[v] l(u, v) procedure update((u, v) ∈ E) dist(v) = min{dist(v), dist(u) + l(u, v)} Ý tưởng: Khoảng cách từ s tới v không thể lớn hơn khoảng cách từ s tới u, cộng với l(u, v). 41 / 52 procedure update((u, v) ∈ E) dist(v) = min{dist(v), dist(u) + l(u, v)} Câu hỏi Giả sử dist(S) = dist(A) = dist(B) = ∞. Ta cần dùng hàm update() mấy lần thì tìm được khoảng cách ngắn nhất từ S đến A? S A B 3 4 −2 42 / 52 Dãy update để tìm đường đi ngắn nhất ▶ Lấy một đỉnh T bất kỳ và xét đường đi ngắn nhất từ S tới T: S u1 u2 · · · uk T ▶ Đường đi này có nhiều nhất |V| − 1 đỉnh. Tại sao? Quan sát Mọi cách gọi update trên dãy cạnh có chứa dãy con (S, u1), (u1, u2), . . . , (uk,T) đều tính đúng khoảng cách từ S tới T. Tại sao? 43 / 52 Thuật toán Bellman-Ford procedure shortest-paths(G, l, s) Input: đồ thị có hướng G = (V,E); độ dài các cạnh {le : e ∈ E} mà không có chu trình âm; đỉnh s ∈ V Output: Với mỗi đỉnh u đến được từ s, dist(u) = khoảng cách từ s tới u. for all u ∈ V: dist(u) = ∞ prev(u) = nil (chưa sử dụng) dist(s) = 0 repeat |V| − 1 times: for all edges e ∈ E: update(e) 44 / 52 Ví dụ P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 118 4.6 Shortest paths in the presence of negative edges Figure 4.13 The Bellman-Ford algorithm for single-source shortest paths in general graphs. procedure shortest-paths(G , l, s) Input: Directed graph G = (V, E ); edge lengths {le : e ∈ E } with no negative cycles; 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) =∞ prev(u) = nil dist(s) = 0 repeat |V |− 1 times: for all e ∈ E: update(e) Figure 4.14 The Bellman-Ford algorithm illustrated on a sample graph. E B A G F D S C 3 1 1 −2 2 10 −1 −1 −4 1 8 Iteration Node 0 1 2 3 4 5 6 7 S 0 0 0 0 0 0 0 0 A ∞ 10 10 5 5 5 5 5 B ∞ ∞ ∞ 10 6 5 5 5 C ∞ ∞ ∞ ∞ 11 7 6 6 D ∞ ∞ ∞ ∞ ∞ 14 10 9 E ∞ ∞ 12 8 7 7 7 7 F ∞ ∞ 9 9 9 9 9 9 G ∞ 8 8 8 8 8 8 8 A note about implementation: for many graphs, the maximum number of edges in any shortest path is substantially less than |V |− 1, with the result that fewer rounds of updates are needed. Therefore, it makes sense to add an extra check to the shortest-path algorithm, to make it terminate immediately after any round in which no update occurred. 4.6.2 Negative cycles If the length of edge (E , B) in Figure 4.14 were changed to −4, the graph would have a negative cycle A→ E → B → A. In such situations, it doesn’t make sense P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO das23402 Ch04 GTBL020-Dasgupta-v10 August 12, 2006 1:48 118 4.6 Shortest paths in the presence of negative edges Figure 4.13 The Bellman-Ford algorithm for single-source shortest paths in general graphs. procedure shortest-paths(G , l, s) Input: Directed graph G = (V, E ); edge lengths {le : e ∈ E } with no negative cycles; vert x s ∈ V Outp :For all vertices u reachable from s, dist(u) is set to he distance from s to u. for all u ∈ V: dist(u) =∞ prev(u) = nil dist( ) = 0 repeat |V |− 1 times: for all e ∈ E: update(e) Figure 4.14 The Bellman-Ford algorithm illustrated on a sample graph. E B A G F D S C 3 1 1 −2 2 10 −1 −1 −4 1 8 Itera ion Node 0 1 2 3 4 5 6 7 S 0 0 0 0 0 0 0 0 A ∞ 10 10 5 5 5 5 5 B ∞ 10 6 5 5 5 C ∞ 11 7 6 6 D ∞ ∞ 14 10 9 E ∞ 12 8 7 7 7 7 F ∞ 9 9 9 9 9 9 G ∞ 8 8 8 8 8 8 8 A note about implementation: for many graphs, the maximu number of edg s in any shortest path is sub tanti lly less than |V |− 1, with the result tha fewer rounds of updates are need d. Therefo , it makes s n to add an extra che k to the s ortest-path lgorithm, to make it terminate immediately after any round in which no update occurred. 4.6.2 Negative cycles If the length of edg (E , B) in Figure 4.14 were changed to −4, the graph would have negative cycle A→ E → B → A. In such situations, it doesn’t make sense 45 / 52 Câu hỏi Làm thế nào để tìm được đường đi ngắn nhất theo thuật toán Bellman-Ford? 46 / 52 Kiểm tra sự tồn tại của chu trình độ dài âm? ▶ Bài toán đường đi ngắn nhất từ s đến t sẽ không có ý nghĩa nếu từ s đến t có thể đi qua chu trình độ dài âm. ▶ Trong thuật toán Bellman-Ford, thay vì dừng sau |V|−1 vòng lặp, ta thực hiện thêm một lần nữa. ▶ Đồ thị có chu trình độ dài âm nếu và chỉ nếu tồn tại đỉnh v mà dist[v] vẫn bị giảm sau vòng cuối. 47 / 52 Nội dung Khoảng cách và tìm kiếm theo chiều rộng Thuật toán Dijkstra Cài đặt hàng đợi ưu tiên Đường đi ngắn nhất khi có cạnh độ dài âm Đường đi ngắn nhất trong một DAG Thuật toán Bellman-Ford cho DAG S A B C3 2 −2 −2−1 Trong DAG, cần update những cạnh nào? 49 / 52 S A B C3 2 −2 −2−1 Tính chất Với mọi đường đi của DAG, các đỉnh xuất hiện theo thứ tự topo. 50 / 52 procedure dag-shortest-paths(G, l, s) Input: DAG G = (V,E); độ dài các cạnh {le : e ∈ E}; đỉnh s ∈ V Output: Với mỗi đỉnh u đến được từ s, dist(u) được đặt bằng khoảng cách từ s tới u. for all u ∈ V: dist(u) = ∞ prev(u) = nil dist(s) = 0 Sắp topo các đỉnh của G for each u ∈ V, theo thứ tự topo: for all edges (u, v) ∈ E: update(u, v) 51 / 52 S A B C3 2 −2 −2−1 Bài tập Hãy liệt kê các lệnh update theo thuật toán Bellman-Ford cho DAG? 52 / 52