If Dijkstra's algorithm is performed on the graph with vertex set
{
0
,
1
,
2
,
3
,
4
,
5
}
and adjacency matrix given below, what is the sequence of edges added to the result (shortest path tree).

Use vertex 0 as a source. We break ties between vertices by picking the vertex with lower index. For example, EXTRACT-MIN returns vertex 1 before vertex 2, if both vertices have the same minimum estimate.

(
0

8

5

9

6

3

8

0

2

2

5

2

5

2

0

3

1

7

9

2

3

0

1

9

6

5

1

1

0

9

3

2

7

9

9

0
)

Question

If Dijkstra's algorithm is performed on the graph with vertex set 
{
0
,
1
,
2
,
3
,
4
,
5
}
 and adjacency matrix given below, what is the sequence of edges added to the result (shortest path tree).

Use vertex 0 as a source.  We break ties between vertices by picking the vertex with lower index.  For example, EXTRACT-MIN returns vertex 1 before vertex 2, if both vertices have the same minimum estimate.

(
0
	
8
	
5
	
9
	
6
	
3

8
	
0
	
2
	
2
	
5
	
2

5
	
2
	
0
	
3
	
1
	
7

9
	
2
	
3
	
0
	
1
	
9

6
	
5
	
1
	
1
	
0
	
9

3
	
2
	
7
	
9
	
9
	
0
)

BlackTom AI · Accepted Answer

We are asked to determine the sequence of edges added to the shortest-path tree by Dijkstra's algorithm starting from vertex 0, using the given 6-vertex graph and its adjacency matrix. Since the provided data for answer options is empty, there are no alternative choices to evaluate; instead, I'll walk through the algorithm step by step and derive the tree explicitly, showing why the listed sequence would be the resulting one.

First, interpret the adjacency matrix as the undirected weighted graph with vertices {0,1,2,3,4,5} and weights given by the matrix rows/columns. The matrix appears to be:
- Row 0: 0, 8, 5, 9, 6, 3
- Row 1: 8, 0, 2, 2, 5, 2
- Row 2: 5, 2, 0, 3, 1, 7
- Row 3: 9, 2, 3, 0, 1, 9
- Row 4: 6, 5, 1, 1, 0, 9
- Row 5: 3, 2, 7, 9, 9, 0
From vertex 0, the initial distances are: dist(0)=0, dist(1)=8, dist(2)=5, dist(3)=9, dist(4)=6, dist(5)=3, with predecessors undefined.

Step 1: Extract the minimum unvisited vertex. The smallest distance is 3 at vertex 5, so the first edge added to the tree is (0, 5). Update neighbors of 5:
- To 1: weight 2, so dist(1) can be updated to 3+2=5 via 5; set predecessor of 1 to 5.
- To 2: weight 7, candidate 3+7=10, not better than current dist(2)=5.
- To 3: weight 9, candidate 3+9=12, not better than 9.
- To 4: weight 9, candidate 3+9=12, not better than 6.

Current distances (unvisited): 1:5 (pred 5), 2:5 (pred 0), 3:9 (pred 0), 4:6 (pred 0).

Step 2: Extract the next minimum. We have dist(1)=5 and dist(2)=5; ties broken by lower index, so vertex 1 is chosen next. The corresponding edge in the tree is (5, 1). Update neighbors of 1:
- To 2: weight 2, candidate dist = 5+2 = 7, which is worse than current dist(2)=5, so no update.
- To 3: weight 2, candidate dist = 5+2 = 7, better than current dist(3)=9, so update dist(3)=7 with predecessor 1.
- To 4: weight 5, candidate dist = 5+5 = 10, worse than dist(4)=6.
- To 5: weight 2, candidate dist = 5+2 = 7, but 5 already visited.

Now unvisited distances: 2:5 (pred 0), 3:7 (pred 1), 4:6 (pred 0).

Step 3: Extract the next minimum. Vertex 2 has dist 5, which is the smallest. The tree edge is (0, 2). Update neighbors of 2:
- To 3: weight 3, candidate dist = 5+3 = 8, worse than current dist(3)=7, so no update.
- To 4: weight 1, candidate dist = 5+1 = 6, equal to current dist(4)=6. Depending on tie-handling, you might keep the existing predecessor (0) or update to 2; in the given solution, the predecessor remains as 0, since the distance is equal and no explicit update is described.
- To 5: weight 7, candidate dist = 5+7 = 12, worse than dist(5)=3.

Distances now: 4:6 (pred 0), 3:7 (pred 1).

Step 4: Extract the next minimum. Vertex 4 has dist 6, the smallest among remaining. The tree edge is (0, 4). Update neighbors of 4:
- To 3: weight 1, candidate dist = 6+1 = 7, equal to current dist(3)=7. Since the current predecessor is 1 and the new path would come from 4, this is an equal alternative; we typically keep the existing predecessor unless the algorithm specifies updating on ties. So dist(3) remains 7 with pred 1.
- Other neighbors do not improve distances.

Remaining: 3 with dist 7 (pred 1).

Step 5: Extract the next minimum. Vertex 3 is selected with dist 7; its predecessor is 1, so the tree edge is (1, 3). Update neighbors of 3, but no unvisited vertex receives a shorter distance through 3.

All vertices are now visited. The sequence of edges added to form the shortest-path tree, in the order of extraction, is:
- (0, 5)
- (5, 1)
- (0, 2)
- (0, 4)
- (1, 3)

Thus, the derived edge sequence matches the provided sequence: (0, 5), (5, 1), (0, 2), (0, 4), (1, 3).

CS5800.18622.202610 Quiz 10

查看解析

登录即可查看完整答案

类似问题

Question at position 4 Which route computation algorithm is used by the OSPF routing mechanism?DijkstraBellman-FordNone of ThemDSR

We worked on Dijkstra's algorithm for CC12. You may assume the MinHeap class has been correctly implemented. Given the following complete implementation, which line contains a bug? Check the comments for LINE1, LINE 2, LINE 3

S_PATH_1 Using the graph and the partially completed table, and Dijkstra's Algorithm, which vertex is our starting vertex?

We worked on Dijkstra's algorithm for CC12. You may assume the MinHeap class has been correctly implemented. Given the following incomplete implementation, please choose correct code segment to complete it.

更多留学生实用工具

考试浏览器助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单