在具有加权顶点的图中查找路径
Find path in graph with weighted vertices
我有下图，其中每个顶点都有一个关联的 "probability"
(graph with weighted nodes).
我想找到从节点0到最后一个节点（最高索引，这里是5）的路径，它具有最高的乘数概率。在此图中，最佳路径为 0-1-4-5，概率为 0.72。
我考虑过使用 BFS 找到开始节点和结束节点之间的所有路径，然后乘以每个节点的概率，但我认为这种方法对所有图都适用太天真了。我如何使用 python?
解决这个问题
正如 Julien 所建议的，Dijkstra's algorithm 将是一个好的开始。您的问题与普通 Dijkstra 的问题有两点不同。
Dijkstra 算法最小化权重之和。为了最大化概率的乘积，您可以将每个权重 p 映射到 -log(p)。快速证明：最大化 (x1*x2*...*xn) 的乘积与最大化 log(x1*x2*...*xn) 相同，因为 log 是 monotonically increasing。 argmax(log(x1*x2*...*xn)) = argmax(log(x1)+log(x2)+...+log(xn)) = argmin(-log(x1)-log(x2)-...-log(xn)))。请注意，如果您想要结果概率，您可以通过采用 10^(-c) 来反转结果，其中 c 是 Dijkstra 使用上述减少的 returned 的最小成本（假设您采用了对数以 10 为底）。另请注意，如果任何概率为 0，则 log(0) 未定义，因此您应该通过使权重无限大来处理此问题（因此路径永远不会通过该节点）。
Dijkstra 使用加权边，而您有加权节点。但这是从加权节点到加权边的简单简化。用 edge_weight(u,v) = vertex_weight(v) 定义从 u 到 v 的边的权重。从你的图片来看，你有一个无向图，所以你需要用两个有向边替换每个无向边，使用与上述相同的权重（注意两个顶点 u 和 [=20 之间的两条边=] 将有不同的权重，除非 vertex_weight(u) == vertex_weight(v))。此外，如果您想 return 最短路径的值，则需要将 vertex_weight(source_vertex) 添加到最终成本，因为在减少时会跳过此成本。
我有下图，其中每个顶点都有一个关联的 "probability" (graph with weighted nodes).
我想找到从节点0到最后一个节点（最高索引，这里是5）的路径，它具有最高的乘数概率。在此图中，最佳路径为 0-1-4-5，概率为 0.72。
我考虑过使用 BFS 找到开始节点和结束节点之间的所有路径，然后乘以每个节点的概率，但我认为这种方法对所有图都适用太天真了。我如何使用 python?
解决这个问题正如 Julien 所建议的，Dijkstra's algorithm 将是一个好的开始。您的问题与普通 Dijkstra 的问题有两点不同。
Dijkstra 算法最小化权重之和。为了最大化概率的乘积，您可以将每个权重
p映射到-log(p)。快速证明：最大化(x1*x2*...*xn)的乘积与最大化log(x1*x2*...*xn)相同，因为log是 monotonically increasing。argmax(log(x1*x2*...*xn)) = argmax(log(x1)+log(x2)+...+log(xn)) = argmin(-log(x1)-log(x2)-...-log(xn)))。请注意，如果您想要结果概率，您可以通过采用10^(-c)来反转结果，其中c是 Dijkstra 使用上述减少的 returned 的最小成本（假设您采用了对数以 10 为底）。另请注意，如果任何概率为 0，则log(0)未定义，因此您应该通过使权重无限大来处理此问题（因此路径永远不会通过该节点）。Dijkstra 使用加权边，而您有加权节点。但这是从加权节点到加权边的简单简化。用
edge_weight(u,v) = vertex_weight(v)定义从u到v的边的权重。从你的图片来看，你有一个无向图，所以你需要用两个有向边替换每个无向边，使用与上述相同的权重（注意两个顶点u和 [=20 之间的两条边=] 将有不同的权重，除非vertex_weight(u) == vertex_weight(v))。此外，如果您想 return 最短路径的值，则需要将vertex_weight(source_vertex)添加到最终成本，因为在减少时会跳过此成本。