确定加权图中最佳路径的算法
Algorithm to determine optimal path in weighted graph
这是我的测试练习题，我检查了加权图和一些相关材料，但无法开始，所以需要一些想法来开始。
假设你想从你在节点 s 的房子到你伴侣的房子
在 加权图 G = (V,E,w) 中节点 t 的房屋。但是你想去当地的 Fish'n
如果可以在不增加路径长度的情况下将筹码放置在节点 u
超过 20%。
(a) 描述一种有效的算法，它可以确定最佳的 s → t 路径，前提是您更愿意沿途在 u 处停下来（如果这样做的成本不是过高的话）。 （它应该要么
return从s到t的最短路径或者从s到t包含u的最短路径，取决于
在这种情况下。）你应该让你的算法运行尽可能高效
试试这个 Dijkstra algorithm。找到从 s 到 t、s 到 u 和 u 到 t 的最短路径。然后，在数学的一点帮助下（s 到 u + u 到 t > s 到 t * 1.20）你可以看到你的答案。干杯。
这是我的测试练习题，我检查了加权图和一些相关材料，但无法开始，所以需要一些想法来开始。
假设你想从你在节点 s 的房子到你伴侣的房子 在 加权图 G = (V,E,w) 中节点 t 的房屋。但是你想去当地的 Fish'n 如果可以在不增加路径长度的情况下将筹码放置在节点 u 超过 20%。
(a) 描述一种有效的算法，它可以确定最佳的 s → t 路径，前提是您更愿意沿途在 u 处停下来（如果这样做的成本不是过高的话）。 （它应该要么 return从s到t的最短路径或者从s到t包含u的最短路径，取决于 在这种情况下。）你应该让你的算法运行尽可能高效
试试这个 Dijkstra algorithm。找到从 s 到 t、s 到 u 和 u 到 t 的最短路径。然后，在数学的一点帮助下（s 到 u + u 到 t > s 到 t * 1.20）你可以看到你的答案。干杯。