最短路径(shortest path)之Floyd算法
最短路径(shortest path)之Floyd算法
千面人 发表于1年前
最短路径(shortest path)之Floyd算法
  • 发表于 1年前
  • 阅读 6
  • 收藏 0
  • 点赞 0
  • 评论 0

标题:腾讯云 新注册用户域名抢购1元起>>>   

摘要: Floyd求解最短路径实在太漂亮了,忍不住要赞一下。

Floyd算法求解最短路径应该是本科数据结构的课程,以前没什么感觉,经过多年,再次看到,发现实在太漂亮了,形式如此简洁,忍不住要赞下:

/* Floyd算法,求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]。 */ 
void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D)
{ 
    int v,w,k; 
    for(v=0; v<G.numVertexes; ++v)            /* 初始化D与P */ 
    { 
        for(w=0; w<G.numVertexes; ++w) 
        {
            (*D)[v][w]=G.arc[v][w];          /* D[v][w]值即为对应点间的权值 */
            (*P)[v][w]=w;                    /* 初始化P */
        }
    }
    for(k=0; k<G.numVertexes; ++k) 
    {
        for(v=0; v<G.numVertexes; ++v) 
        { 
            for(w=0; w<G.numVertexes; ++w) 
            {
                if ((*D)[v][w]>(*D)[v][k]+(*D)[k][w])
                {
                    /* 如果经过下标为k顶点路径比原两点间路径更短 */
                    (*D)[v][w]=(*D)[v][k]+(*D)[k][w];     /* 将当前两点间权值设为更小的一个 */
                    (*P)[v][w]=(*P)[v][k];                /* 路径设置为经过下标为k的顶点 */
                }
            }
        }
    }
}

参考资料:

【1】数据结构之最短路径(Floyd) http://blog.chinaunix.net/uid-26548237-id-3834873.html 

共有 人打赏支持
粉丝 12
博文 38
码字总数 21269
×
千面人
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: