双图＆QUOT;在＆QUOT最短路径;与更改的数目有限 [英] Shortest path in "two-graph" with limited number of changes

问题描述

比方说，我们有两个导演，在一组顶点（第一张图再presents例如铁路公路和第二个积极的加权图 - 公交专用道;顶点是公交车站或铁路公路站或都）。我们需要找到从A到B的最短路径，但我们无法改变的传输类型超过N次。

Let's say we have two directed and positive-weighted graphs on one set of vertices (first graph represents for example rail-roads and the second one - bus lanes; vertices are bus stops or rail-road stations or both). We need to find the shortest path from A to B, but we can't change the type of transport more than N times.

我试图修改Dijkstra算法，但它的一些不那么均值和复杂的图的工作只是，我想我需要尝试不同的东西。

I was trying to modify the Dijkstra's algorithm, but it's working only on a few "not-so-mean-and-complicated" graphs and I think I need to try something different.

如何最好地重新present了两图，以及如何管理在遍历图的变化量有限？是否有一个适应Dijkstra算法在这一种可能性？任何想法和线索会有所帮助。

How to best represent that "two-graph" and how to manage the limited amount of changes in traversing the graph? Is there a possibility to adapt Dijkstra's algorithm in this one? Any ideas and clues will be helpful.

编辑：嗯，我忘了一件事（我认为这是非常重要）：N = 0,1,2，...;我们可以拿出我们喜欢的任何图形重新presentation当然可以存在每两个节点之间的最大4个边缘（1公交专用道和1个铁路在一个方向，和1个公交专用道和1个铁路在第二方向）

Well I forgot one thing (I think it's quite important): N = 0,1,2,...; we can come up with any graph representation we like and of course there can exist maximum 4 edges between every two nodes (1 bus lane and 1 railroad in one direction, and 1 bus lane and 1 railroad in the second direction).

推荐答案

我不认为这是最好的方式，但您可以创建节点如下：

I don't think it is the best way, but you can create Nodes as follow:

Node:(NodeId, GraphId, correspondenceLeftCount)

（节点总数将 number_of_initial_nodes * number_of_graphs * number_of_correspondences_allowed ）

所以：

有关的边缘，其中 GraphId 不改变， correspondenceLeftCount 不改变都不是。
您添加一个新的边缘为对应关系：

For edge where GraphId doesn't change, correspondenceLeftCount doesn't change neither. You add a new Edge for correspondance:

（节点Id，Graph1，correspondenceLeftCount） - >（节点Id，Graph2，correspondenceLeftCount - 1）`

(NodeId, Graph1, correspondenceLeftCount) -> (NodeId, Graph2, correspondenceLeftCount - 1)`

和为请求A-> B：
你的起点是（A，graph1，maxCorrespondenceLeftCount）和（A，graph2，maxCorrespondenceLeftCount）。结果
而你的终点是（B，graph1，0） ... （B，graph1，maxCorrespondenceLeftCount） ，（B，graph2，0） ... （B，graph2，maxCorrespondenceLeftCount）。

And for the request A->B: Your start point are (A, graph1, maxCorrespondenceLeftCount) and (A, graph2, maxCorrespondenceLeftCount).
And your end points are (B, graph1, 0), ... , (B, graph1, maxCorrespondenceLeftCount), (B, graph2, 0), ... , (B, graph2, maxCorrespondenceLeftCount).

所以，你可能不得不调整你的Dijkstra算法实现了的结束条件的，并且能够插入多个起点。

So you may to have to adapt your Dijkstra implementation for the end condition, and to be able to insert more than one start point.

这篇关于双图＆QUOT;在＆QUOT最短路径;与更改的数目有限的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！