知识卡片

普通读书笔记卡 · 3645.i

全点对距离通常用矩阵输出

理解等级:中级

全点对最短路把每个源点到每个目标的最短权重放进 n×n 矩阵,第 i 行第 j 列代表 δ(i,j)。

若需要实际路径,还须保留额外前驱信息。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第23章《所有结点对的最短路径》(OEBPS/chapter023.xhtml,文本字符[0,5000))。 - 结论依据:原文给出表格输出、矩阵元素含义并随后说明前驱矩阵。 - 原始内容:For the all-pairs problem, the output typically takes a tabular form in which the entry in u ’s row and v ’s column is the weight of a shortest path from u to v . You can solve an all-pairs shortest-paths problem by running a