给出了一个直径k我试图找到一种方法，给出最有效的（运行时间）算法，以找到从S（源）到v中任何节点v的最短路径。
我不知道如何使用给定的直径来提高算法的效率？
谢谢你的帮助。
最佳答案
直径一点用也没有，你可以忽略它。
举一个极端的例子，一个完全连通的图它的直径是1（每个节点只有一个链接）。
但是，您可以想象，除了1->2->3->4->5->n这样的权重很低的路径外，所有的边都有很大的权重，因此路径必须通过低成本的边，因此必须通过所有节点。
如果直径以重量表示，则可以优化dijkstra以忽略任何超过直径的更新。
关于algorithm - 直径为k <| V |的连通加权有向图，找到最短路径，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37614629/