直径 k< |V| 的连通加权有向图，求最短路径
connected weighted directed graph with diameter k< |V|, find the shortest path
给你一个连通的加权有向图 G = (V,E)，直径 k < |V|和
我试图找到一种方法来提供最有效的（运行 时间）算法来找到从 S（源）到 V 中任何节点 v 的最短路径。
我不知道如何使用给定的直径来提高算法的效率？
感谢您的帮助。
直径根本没有帮助，你可以忽略它。
举个极端的例子，全连接图。它的直径将为 1（每个节点只有一个 link 远）。
但是你可以想象，除了像 1->2->3->4->5->..->N 这样的路径具有非常低的权重，所有的边都具有非常大的权重，因此该路径必须通过低成本边，因此通过所有节点。
如果直径以重量表示，您可以优化 dijkstra 以忽略任何超过直径的更新。
给你一个连通的加权有向图 G = (V,E)，直径 k < |V|和 我试图找到一种方法来提供最有效的（运行 时间）算法来找到从 S（源）到 V 中任何节点 v 的最短路径。 我不知道如何使用给定的直径来提高算法的效率？
感谢您的帮助。
直径根本没有帮助，你可以忽略它。 举个极端的例子，全连接图。它的直径将为 1（每个节点只有一个 link 远）。
但是你可以想象，除了像 1->2->3->4->5->..->N 这样的路径具有非常低的权重，所有的边都具有非常大的权重，因此该路径必须通过低成本边，因此通过所有节点。
如果直径以重量表示，您可以优化 dijkstra 以忽略任何超过直径的更新。