弗洛伊德的算法（Floyd’s algorithm ）

来源：学生作业帮编辑：神马作文网作业帮分类：英语作业时间：2024/11/11 23:52:31

弗洛伊德的算法（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]

说下答案, 也说下怎么做的

假设这个图的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｝的最短路径.
再问：还是不明白啊
再答：最开始的时候，map中的值是两点间的直接距离，可以看作是不使用中间节点的最短路径长度。最外层循环执行过一次以后，map中记录的就是允许使用节点0做中间节点的最短路径长度。到这里都可以理解吧？那么假设map目前存的是允许使用节点0...k-1 的情况下，节点之间的最短路径。那么在允许使用节点0...k的情况下i,j之间的最短路径就是min{map[i][j], map[i][k]+map[k][j]} 还有哪里不明白，请指明
再问：我那题目应该不是叫我写代码的吧，我想要那个答案
再答：依然用矩阵表示两点之间的最短路径： 0 9 2 5 7 10 0 12 3 5 10 7 0 3 5 7 4 9 0 2 5 14 7 10 0

弗洛伊德算法Floyd和迪杰斯特拉Dijkstra算法 Floyd算法与Dijkstra算法的不同轮盘赌for遗传算法（genetic algorithm）中,求最小的cost,如果cost有正有负, 对于同一个邻接矩阵,用floyd与dijkstra算法解出不同的结果 pink floyd的简介用弗洛伊德算法求最短路径计算机算法的题Develop an algorithm which takes as input a single 9- wish you were here（PINK FLOYD）讲的是什么? Pink Floyd的《If》歌词请推荐几本S.弗洛伊德和尼采的书类程序设计语言,PDL,N-S图,algorithm 弗洛伊德的个人名言