弗洛伊德的算法(Floyd’s algorithm )b.) Consider a weighted directed graph G with 5 vertices {v1,v2,v3,v4,v5}.The weights of the edges are shown in the matrix below.Apply Floyd’s algorithm to G to find the shortest path length for all pa
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/05 15:37:34
![弗洛伊德的算法(Floyd’s algorithm )b.) Consider a weighted directed graph G with 5 vertices {v1,v2,v3,v4,v5}.The weights of the edges are shown in the matrix below.Apply Floyd’s algorithm to G to find the shortest path length for all pa](/uploads/image/z/11698091-35-1.jpg?t=%E5%BC%97%E6%B4%9B%E4%BC%8A%E5%BE%B7%E7%9A%84%E7%AE%97%E6%B3%95%EF%BC%88Floyd%E2%80%99s+algorithm+%EF%BC%89b.%29+Consider+a+weighted+directed+graph+G+with+5+vertices+%7Bv1%2Cv2%2Cv3%2Cv4%2Cv5%7D.The+weights+of+the+edges+are+shown+in+the+matrix+below.Apply+Floyd%E2%80%99s+algorithm+to+G+to+find+the+shortest+path+length+for+all+pa)
弗洛伊德的算法(Floyd’s algorithm )b.) Consider a weighted directed graph G with 5 vertices {v1,v2,v3,v4,v5}.The weights of the edges are shown in the matrix below.Apply Floyd’s algorithm to G to find the shortest path length for all pa
弗洛伊德的算法(Floyd’s algorithm )
b.) Consider a weighted directed graph G with 5 vertices {v1,v2,v3,v4,v5}.The weights of the edges are shown in the matrix below.
Apply Floyd’s algorithm to G to find the shortest path length for all pairs of vertices.[20 marks]
说下答案, 也说下怎么做的
弗洛伊德的算法(Floyd’s algorithm )b.) Consider a weighted directed graph G with 5 vertices {v1,v2,v3,v4,v5}.The weights of the edges are shown in the matrix below.Apply Floyd’s algorithm to G to find the shortest path length for all pa
假设这个图的weight matrix存在map[5][5]中,
for (int k=0; k<5; k++)for (int i=0; i<5; i++)
for (int j=0; j<5; j++) if (i != j) {
if (map[i][k] + map[k][j] < map[i][j])
map[i][j] = map[i][k] + map[k][j];
}
处理完之后map[i][j]存的就是i,j之间的最短路径长度.
简单的说,当执行完一次最外层循环时,map记录的时i,j之间允许使用中间节点{0, ..., k}的最短路径.