有向图中的非简单路径。

• 下载 GraphPuzzle.zip - 2.5 MB

引言

在本文中，我想讨论如何在有向图中找到从起始节点到结束节点的所有非简单路径。非简单路径是指可以包含循环且边权重可能为负的路径。寻找有向图中任意两个节点之间所有简单路径的经典问题的解决方案是众所周知的，并且有很多例子；但是，我找不到任何关于如何查找非简单路径的有用的信息。因此，我决定写这篇文章来演示如何解决这个问题。为了让文章更有趣，我将使用一个编程谜题来展示如何解决非简单路径问题。

谜题

一名出租车司机需要在不耗尽汽油的情况下找到一条从一个城市到另一个城市的路线。在每个城市对之间，都有可能出现的乘客愿意为一次行程付费，让司机每次从一个城市到另一个城市都能积累一定的金钱。 有些路线会收取过路费，导致金钱损失。您需要计算一条利润最大化的路线。您的程序需要输入起始城市名称、目的地城市名称、它们之间的距离以及路线可能产生的利润。

示例

假设我们有以下连接

A --------->B 距离：10 利润：40

B --------->C 距离：15 利润：5

C --------->B 距离：15 利润：30

A --------->C 距离：30 利润：50

如果出租车司机有40英里的汽油，并且从A到C行驶，那么最佳行程是A -> B -> C -> B -> C，利润为55。

正如您所见，这是一个复杂的问题：路径必须最大化 利润，可以包含循环， 可以多次访问结束节点 并且 可以具有负权重。显然，像 Dijkstra 或 Bellman-Ford 这样的算法在这里不起作用； 同样，它也不能以与寻找两个任意节点之间简单连接相同的方式来解决。

解决方案

我们想要做的是找到所有从A点到B点的可能路径，其总距离不超过指定的距离。尽管可能涉及循环，并且可以多次访问结束节点，但距离限制使我们能够枚举所有这些路径，因为它们中的每一个都由其长度唯一标识。换句话说，路径的原子性不仅由起始点和结束点决定，还由它们的长度决定。

为了获得从A点开始的所有路径，我们将使用深度优先搜索来遍历图，该搜索从A点开始。 在遍历子节点时，我们将创建一个子节点 -> 父节点的链接，以便知道我们已经访问过的所有边。 在前往该子节点之前，我们必须遍历该链接列表，并确保指定的边在可接受的距离限制内。 当我们到达距离限制内的目标节点时，我们可以存储找到的路径。如果超过距离限制，搜索将开始回溯以查找下一条路径。

   private void Search(Graph g, LinkedList<int> visited)
   {
             var nodes =  g.Adj(visited.Last.Value);
              foreach (var edge in nodes)
              {
                 if (_pathDistance + edge.Distance > _maxDistance)
                      continue;
                                      
                 int w = edge.To;
                  if (w  == _target)
                  {
                      visited.AddLast(w);
                      _pathDistance += edge.Distance;
                      _pathProfit += edge.Profit;
                      SavePath(visited);
                      Print(visited);
                      visited.RemoveLast();
                      _pathDistance -= edge.Distance;
                      _pathProfit -= edge.Profit;
                  }
              }

              foreach (var edge in nodes)
              {
                
                  if (_pathDistance + edge.Distance > _maxDistance)
                  {
                      continue;
                  }
                   
                    int w = edge.To;
                  visited.AddLast(w);
                  _pathDistance += edge.Distance;
                  _pathProfit += edge.Profit;
                  Search(g, visited);
                  visited.RemoveLast();
                  _pathDistance -= edge.Distance;
                  _pathProfit -= edge.Profit;
              }
     }

正如您所看到的， 该问题的解决方案是深度优先搜索，它找到两个顶点之间不超过指定最大距离的所有路径。路径的结束不是简单地由命中目标节点决定，而是由旅行期间可覆盖的距离决定。搜索会跟踪遍历过程中获得的利润。 结果中，每条选定的路径都与其总权重相关联。

当我们知道所有可能的连接后，就可以找到最有利可图的连接。为此，我们将路径存储在优先级队列中。

 
 private void SavePath(LinkedList<int> visited)
 {
            _paths.Add(visited.ToArray());
             
            // priority queue
            _pq.Add(new State(_paths.Count() - 1, _pathProfit, _pathDistance ));
 }

现在，我们可以查询队列以找到最优连接。

 public double BestProfit()
 {
          return _pq.FindMax().Profit;
 }
 

示例

我们向程序输入以下连接

起始 结束 距离 利润

Alicetown Bobville 10 50

Alicetown Carolina 30 60

Bobville Carolina 15 5

Carolina Bobville 15 5

Bobville Danburg 20 75

Danburg Bobville 20 40

Bobville Eveland 25 15

Carolina Danburg 10 20

Carolina Eveland 30 20

Danburg Eveland 40 40

Eveland Danburg 20 40

Eveland Frank City 15 -10

Frank City Danburg 10 35

然后，我们请求以下行程