graph - 如何将有向加权图的每条路径转换为等价？（见说明）

Question

我们能否转换有向加权图，使其从指定源到目的地的每条路径都具有相同的成本？每条路径的成本应该等于原始图中的最大成本路径。如何将任何有向加权图转换为这种类型的图？是否可以将每个有向加权图转换为这种类型的图？

图的来源和目的地是预定义的。

Answer 1

可以以这种方式转换图形。

请注意，如果（结果）图的属性比给定顶点 (s和) 之间的所有路径具有相同的成本，则该属性对于位于和d之间的任何路径上的每对顶点都成立。通过检查(or ) 和任何内部 vertex之间的成本可以看出这一点。这样，我们可以说每个顶点的成本为。sdsdxxs

要创建顶点成本：

• 将成本设置s为0,
• 以拓扑顺序传递图并将顶点的成本设置为max predecessor costs + 1。

a -> b以边缘具有成本的方式创建具有所需属性更改边缘成本的图形cost_of_Vertex_b - cost_of_vertex_a。

要获得预定义的成本，请按一个因子缩放所有成本。