知识卡片

普通读书笔记卡 · 3645.h

图直径是最远最短路

理解等级:中级

图的直径取所有有序顶点对最短路权的最大值。

若通信网络强连通且边权为传输时间,它才表示最慢一对节点的最短传递时间;存在不可达点对时,按无穷距离约定直径为∞,不能解释为有限耗时。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第23章 所有结点对的最短路径 · 查看原书依据

      A legitimate application of all-pairs shortest paths is to determine the diameter of a network: the longest of all shortest paths. If a directed graph models a communication network, with the weight of an edge indicating the time required for a message to traverse a communication link, then the diameter gives the longest possible transit time for a message in the network.

    参考来源

    - 位置:《算法导论(第4版)》第23章《所有结点对的最短路径》(OEBPS/chapter023.xhtml,文本字符[0,5000))。 - 结论依据:原文以所有顶点对最短路的最大值定义直径;第22章对不可达点对取∞,因此有限传递时间解释需要强连通前提。 - 原始内容:A legitimate application of all-pairs shortest paths is to determine the diameter of a network: the longest of all shortest paths. If a directed graph models a communication network, with the weight of an edge indicating the time required for a message to traverse a communication link, then the diameter gives the longest possible transit time for a message in the network.