最短路径最大利润
Shortest Path Maximum Profit
假设您有一个无向图 G=(V,E) 和 V 中的两个顶点 s,t，s 不等于 t。 E 中的每条边 e 都有长度和利润。
问题是：
我怎样才能找到 s-t 之间的路径 P=(s,a1,a2,...,t) ，使得路径的总长度尽可能小，利润尽可能大。
使用 Dijkstra 我可以找到第一个约束条件，但是我如何确定第二个约束条件呢？
你可以回溯但是，有没有更快的算法？欢迎任何帮助。
编辑：
首先找到最短路径的值x，然后遍历所有的集合
相同长度 x 的路径，找出一条利润最大的路径。
看这张图：
基本上你正在做的是你有两个数组分别维护长度和利润。
您可以创建另一个数组，该数组的长度与边的利润之比。
因此，该数组将为所有边存储 ratio = length/profit 并使用此 ration 数组，您可以使用 Djikshtra 的算法。
对于 Djikshtra 的算法，使用 V 集作为顶点和数组的比例。使用这个 运行 Djikshtra 的算法。您将得到所需的答案
不是在 Dijkstra 算法中为每个候选路径存储单个值，而是存储一个元组（总长度，总利润）。如果总长度较小，或者总长度相同但总利润较高，则考虑在松弛步骤中选择较短的路径。
这似乎是 multi-objective optimization 的一个例子。
解决此类问题的一种方法是为 lambda 创建一个新变量 L。
但首先，让我们处理利润问题：您的边有长度 l 和利润 p。重新定义所有 p 使得 p'=max(p)-p。现在，您的最大盈利优势的值为零（最低可能），您的最低盈利优势的值为 max(p)（最高可能）。您现在可以找到成本最低的路径。
定义边的权重为 l*L+p'*(1-L)，现在 L 从 0 到 1 变化。根据长度或利润哪个更重要，不同的路径将是最优的。粗略地说，这些路径形成了帕累托最优集。对于 L 的特定值，每个解决方案路径都优于所有其他解决方案路径。为此 L 没有办法在不增加长度的情况下增加利润，或者在不减少利润的情况下减少长度。
请注意，选择 L 的适当值来生成此集合可能不是直截了当的：例如，如果利润数字远大于长度数字，则集合的大部分将聚集在 L 将利润值缩放到与长度值相当的水平。这些 L 值可能很小。
糟糕，看到你的编辑："First find the value x of the shortest path, then over the set of all the paths with the same length x, find one with the maximum profit." 在这种情况下， 是正确的选择。
假设您有一个无向图 G=(V,E) 和 V 中的两个顶点 s,t，s 不等于 t。 E 中的每条边 e 都有长度和利润。
问题是： 我怎样才能找到 s-t 之间的路径 P=(s,a1,a2,...,t) ，使得路径的总长度尽可能小，利润尽可能大。 使用 Dijkstra 我可以找到第一个约束条件，但是我如何确定第二个约束条件呢？
你可以回溯但是，有没有更快的算法？欢迎任何帮助。
编辑： 首先找到最短路径的值x，然后遍历所有的集合 相同长度 x 的路径，找出一条利润最大的路径。
看这张图：
基本上你正在做的是你有两个数组分别维护长度和利润。 您可以创建另一个数组，该数组的长度与边的利润之比。 因此，该数组将为所有边存储 ratio = length/profit 并使用此 ration 数组，您可以使用 Djikshtra 的算法。 对于 Djikshtra 的算法，使用 V 集作为顶点和数组的比例。使用这个 运行 Djikshtra 的算法。您将得到所需的答案
不是在 Dijkstra 算法中为每个候选路径存储单个值，而是存储一个元组（总长度，总利润）。如果总长度较小，或者总长度相同但总利润较高，则考虑在松弛步骤中选择较短的路径。
这似乎是 multi-objective optimization 的一个例子。
解决此类问题的一种方法是为 lambda 创建一个新变量 L。
但首先，让我们处理利润问题：您的边有长度 l 和利润 p。重新定义所有 p 使得 p'=max(p)-p。现在，您的最大盈利优势的值为零（最低可能），您的最低盈利优势的值为 max(p)（最高可能）。您现在可以找到成本最低的路径。
定义边的权重为 l*L+p'*(1-L)，现在 L 从 0 到 1 变化。根据长度或利润哪个更重要，不同的路径将是最优的。粗略地说，这些路径形成了帕累托最优集。对于 L 的特定值，每个解决方案路径都优于所有其他解决方案路径。为此 L 没有办法在不增加长度的情况下增加利润，或者在不减少利润的情况下减少长度。
请注意，选择 L 的适当值来生成此集合可能不是直截了当的：例如，如果利润数字远大于长度数字，则集合的大部分将聚集在 L 将利润值缩放到与长度值相当的水平。这些 L 值可能很小。
糟糕，看到你的编辑："First find the value x of the shortest path, then over the set of all the paths with the same length x, find one with the maximum profit." 在这种情况下，