我们能否转换有向加权图，使其从指定源到目的地的每条路径都具有相同的成本？每条路径的成本应该等于原始图中的最大成本路径。如何将任何有向加权图转换为这种类型的图？是否可以将每个有向加权图转换为这种类型的图？
图的来源和目的地是预定义的。
问问题
61 次
1 回答
0
可以以这种方式转换图形。
请注意，如果（结果）图的属性比给定顶点 (s和) 之间的所有路径具有相同的成本，则该属性对于位于和d之间的任何路径上的每对顶点都成立。通过检查(or ) 和任何内部 vertex之间的成本可以看出这一点。这样，我们可以说每个顶点的成本为。sdsdxxs
要创建顶点成本：
- 将成本设置
s为0, - 以拓扑顺序传递图并将顶点的成本设置为
max predecessor costs + 1。
a -> b以边缘具有成本的方式创建具有所需属性更改边缘成本的图形cost_of_Vertex_b - cost_of_vertex_a。
要获得预定义的成本，请按一个因子缩放所有成本。
于 2017-01-27T06:35:47.700 回答