具有彩色边的加权图中的最短路径

-1

我有一个带有N个veritces和M个边的带权无向图。每条边都有其重量和颜色。整个图表中最多有10种不同的颜色。每次我通过不同颜色的边缘时，我必须支付额外的费用，等于K.给定两个顶点A和B，我想找到它们之间的最短路径。例如，给定具有3个顶点，K = 5和3个边的多个图：（权重3和颜色1的1→2），（权重5和颜色2的1→2），（2→3） 2和颜色2），最短路径的权重是12.我想设计一个算法，可以在相当长的时间内解决这个问题（如O（N）或O（N log N）），但我不知道除了蛮力之外。具有彩色边的加权图中的最短路径

我仍在寻找解决方案。如果有人知道如何解决它，请回复。

约束：

ň< = 10^5

中号< = 10^5

ķ< = 10^5

来源

2016-04-23 user128409235

交叉发表：http://cs.stackexchange.com/q/56688/755，http://stackoverflow.com/q/36808913/781723，http://mathoverflow.net/q/237582/37212 。请[不要在多个网站上发布相同的问题]（http://meta.stackexchange.com/q/64068）。每个社区都应该诚实地回答问题，不要浪费任何人的时间。附：你遇到这种情况的背景是什么？这是一个编程竞赛的问题吗？ –

我投票结束这个问题作为题外话，因为这是从这里交叉发布：http://cs.stackexchange.com/questions/56688/shortest-path-in-a-weighted-graph-with-彩色边缘 –

我说你可以修改Dijkstra's Algorithm做这个。您只需为传递的最后一个颜色的每个顶点存储一个额外的字段，以便当算法需要边的长度时，您可以在该边的颜色不等于最后传递的颜色时添加颜色税。然后，你必须更新该字段。这会在O（M + N log N）时间内完成。

编辑：随着伪代码：

1 function Dijkstra(Graph, source): 
2  dist[source] ← 0 
3 
4  create vertex set Q 
5 
6  for each vertex v in Graph:   
7   if v ≠ source 
8    dist[v] ← INFINITY 
9    prev[v] ← UNDEFINED 
11   Q.add_with_priority(v, dist[v]) 
12 
13  while Q is not empty: 
14   u ← Q.extract_min() 
15   for each neighbor v of u: 
16    if color(prev[u], u) ≠ color(u, v) 
17     alt = dist[u] + length(u, v) + colorTax 
18    else 
19     alt = dist[u] + length(u, v) 
20    if alt < dist[v] 
21     dist[v] ← alt 
22     prev[v] ← u 
23     Q.decrease_priority(v, alt) 
24 
25  return dist[], prev[]

原来，这与使用上一个场甚至没有需要一个新的领域。

来源

2016-04-23 09:46:34

这是我的第一个想法，但我认为它最终会是指数时间算法。如果我有一个非常大的图，从顶点1有100个边到顶点2和从顶点2到100边到顶点3等。 – user128409235

我加入了一些伪代码，我所做的更改不应该对运行产生任何影响时间，这被证明是O（M + N log N）。关于您对一个图形的担心，即在两个顶点之间存在边缘负载的情况下，您可以计算哪条边的长度+可选的colorTax最低，然后使用该边。这不应该太多地影响运行时间。除非你有大量的边缘，但如果是这样的话，无论如何你都不会有很好的运行时间。 –

如我在上一条评论中所解释的，如果存在多条边，则伪代码没有计算挑选哪条边的方法。所以它不输出12或15，它们在两者之间不明确。正如我所提到的，当你做一些计算来找出哪条边最小时，它会输出12. –

对于每个顶点，根据您达到它的颜色（每个副本的传出边相同）将其分成10个不同的顶点。请注意，即使原始图形是无向的，该新图形也是定向的。

然后在这个新图中Dijkstra的算法给你答案。

来源

2016-04-23 12:10:25 ffao

具有彩色边的加权图中的最短路径

回答

相关问题