有向无环图中的最短路径

Question

给我一个字符串，其中每个后续字符对都包含一条边。我的意思是这个字符串：ABBCAD。字符串的边是：

A->B
B->C
A->D

最短路径距离是 A->D

当前的任务是使用上述规则从字符串在内存中构建有向无环图，并找到以根节点为起点的最短路径（在示例中）假设它是 A 标签）以终端节点结束。

NJKUUGHBNNJHYAPOYJHNRMNIKAIILFGJSNAICZQRNM

我收集适合该任务的方法之一是使用深度优先搜索算法。

这不是家庭作业...

Answer 1

这是 Djikstra 算法 的工作。一旦构建了图的表示，就应该很容易产生最低成本的遍历......因为在您的情况下，似乎所有路径都具有相同的成本（1）。

您可以在 CodeProject 上查看，了解 Djikstra 在 C# 中的相当不错的实现。

您能否向我提供此案例的图形表示版本的伪代码？

在此类问题中，有多种方法可以表示图形。如果图中的顶点数量可能很小 - 使用邻接矩阵 用于表示边缘。在这种情况下，您可以只使用 .NET 多维数组。这里的技巧是您需要将用字符标记的顶点转换为序数值。一种方法是编写一个包装类，将字符代码映射到邻接矩阵的索引：

class AdjacencyMatrix
{
    // representation of the adjacency matrix (AM)
    private readonly int[,] m_Matrix;
    // mapping of character codes to indices in the AM
    private readonly Dictionary<char,int> m_Mapping;

    public AdjacencyMatrix( string edgeVector )
    {
        // using LINQ we can identify and order the distinct characters
        char[] distinctChars = edgeVector.Distinct().OrderBy(x => x);

        m_Mapping = distinctChars.Select((c,i)=>new { Vertex = c, Index = i })
                                 .ToDictionary(x=>x.Vertex, x=>x.Index);

        // build the adjacency cost matrix here...
        // TODO: I leave this up to the reader to complete ... :-D
    }

    // retrieves an entry from within the adjacency matrix given two characters
    public int this[char v1, char v2]
    {
        get { return m_Matrix[m_Mapping[v1], m_Mapping[v2]];
        private set { m_Matrix[m_Mapping[v1], m_Mapping[v2]] = value; }
    }
}

Answer 2

对于这种特殊情况，Dijkstra 可以大大简化。我想这样的事情就能解决问题。

class Node {
    public object Value;

    // Connected nodes (directed)
    public Node[] Connections;

    // Path back to the start
    public Node Route;
}

Node BreadthFirstRoute(Node[] theStarts, Node[] theEnds) {
    Set<Node> visited = new Set<Node>();

    Set<Node> frontier = new Set<Node>();
    frontier.AddRange(theStarts);

    Set<Node> ends = new Set<Node>();
    ends.AddRange(theEnds);

    // Visit nodes one frontier at a time - Breadth first.
    while (frontier.Count > 0) {

        // Move frontier into visiting, reset frontier.
        Set<Node> visiting = frontier;
        frontier = new Set<Node>();

        // Prevent adding nodes being visited to frontier
        visited.AddRange(visiting);

        // Add all connected nodes to frontier.
        foreach (Node node in visiting) {               
            foreach (Node other in node.Connections) {
                if (!visited.Contains(other)) {
                    other.Route = other;
                    if (ends.Contains(other)) {
                        return other;
                    }
                    frontier.Add(other);
                }
            }
        }
    }

    return null;
}

Answer 3

只是为了记录。这是您的图表示例：

其中从 A 到 M 的最短路径标记为蓝色。

这是 Mathematica 中的一个非常短的程序：

a = StringSplit["NJKUUGHBNNJHYAPOYJHNRMNIKAIILFGJSNAICZQRNM", ""]
b = Table[a[[i]] -> a[[i + 1]], {i, Length@a - 1}]
vertexNumber[g_, vName_] := Position[ Vertices[g, All], vName][[1, 1]];
Needs["Combinatorica`"]  

c     = ToCombinatoricaGraph[b]
sp    = ShortestPath[c, vertexNumber[c, "A"], vertexNumber[c, "M"]]
vlsp  = GetVertexLabels[c, sp]
vlspt = Table[{vlsp[[i]], vlsp[[i + 1]]}, {i, Length@vlsp - 1}] 

GraphPlot[b, VertexLabeling -> True, ImageSize -> 250, 
         DirectedEdges -> True, Method -> {"SpringEmbedding"}, 
         EdgeRenderingFunction ->
           (If[Cases[vlspt, {First[#2], Last[#2]}] == {}, 
                {Red, Arrowheads[Medium], Arrow[#1, .1]}, 
                {Blue, Arrowheads[Medium], Arrow[#1, .1]}] &)]

Answer 4

LBushkin的回答是正确的。埃里克·利珀特 (Eric Lippert) 关于在 C# 中实现 A* 算法 的系列。 A* 是 Dijkstra 算法的更一般情况：如果您的成本估计函数始终返回 0，则它与 Dijkstra 完全相同。

Answer 5

另一种选择是使用实现了各种最短路径算法的图形库。我过去使用过并发现很好的一个是 QuickGraph。该文档非常好。例如，这里是一个页面解释如何使用 Dijkstra 算法的文档。

Answer 6

由于您的图是非循环的，因此可以使用维特比算法，按拓扑顺序访问状态并更新前面顶点（状态）的成本。

下面的代码实现了搜索算法和数据结构。根据最初的问题，我不能 100% 确定有效的定义。但修改代码以构建其他拓扑并使用 DAG 解决各种动态编程任务应该是直接的。

在计算状态势时将外部 for 循环更改为带有队列的 while 循环将允许通过更改队列规则轻松地使用不同的最短路径算法。例如，基于二进制堆的队列将给出 Dijkstra 算法，或者 FIFO 队列将给出 Bellman-Ford 算法。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DAGShortestPath
{
  class Arc
  {
    public Arc(int nextstate, float cost)
    {
      Nextstate = nextstate;
      Cost = cost;
    }
    public int Nextstate { get; set; }
    public float Cost { get; set; }
  };

  class State
  {
    public bool Final { get; set; }
    public List<Arc> Arcs { get; set; }

    public void AddArc(int nextstate, float cost)
    {
      if (Arcs == null)
        Arcs = new List<Arc>();
      Arcs.Add(new Arc(nextstate, cost));
    }
  }
  class Graph
  {
    List< State > _states  = new List< State >();
    int _start = -1;

    public void AddArc(int state, int nextstate, float cost)
    {
      while (_states.Count <= state)
        AddState();
      while (_states.Count <= nextstate)
        AddState();
      _states[state].AddArc(nextstate, cost);
    }

    public List<Arc> Arcs(int state)
    {
      return _states[state].Arcs;
    }

    public int AddState()
    {
      _states.Add(new State());
      return _states.Count - 1;
    }

    public bool IsFinal(int state)
    {
      return _states[state].Final;
    }

    public void SetFinal(int state)
    {
      _states[state].Final = true;
    }

    public void SetStart(int start)
    {
      _start = -1;
    }

    public int NumStates { get { return _states.Count; } }

    public void Print()
    {
      for (int i = 0; i < _states.Count; i++)
      { 
        var arcs = _states[i].Arcs;
        for (int j = 0; j < arcs.Count; j++)
        {
          var arc = arcs[j];          
          Console.WriteLine("{0}\t{1}\t{2}", i, j, arc.Cost);
        }
      }
    }
  }

  class Program
  {
    static List<int> ShortertPath(Graph graph)
    {
      float[] d = new float[graph.NumStates];
      int[] tb = new int[graph.NumStates];
      for (int i = 0; i < d.Length; i++)
      {
        d[i] = float.PositiveInfinity;
        tb[i] = -1;
      }      
      d[0] = 0.0f;
      float bestscore = float.PositiveInfinity;
      int beststate = -1;

      for (int i = 0; i < graph.NumStates; i++)
      {
        if (graph.Arcs(i) != null)
        {
          foreach (var arc in graph.Arcs(i))
          {
            if (arc.Nextstate < i)
              throw new Exception("Graph is not topologically sorted");

            float e = d[i] + arc.Cost;
            if (e < d[arc.Nextstate])
            {
              d[arc.Nextstate] = e;
              tb[arc.Nextstate] = i;

              if (graph.IsFinal(arc.Nextstate) && e < bestscore)
              {
                bestscore = e;
                beststate = arc.Nextstate;
              }
            }
          }
        }
      }

      //Traceback and recover the best final sequence

      if (bestscore == float.NegativeInfinity)
        throw new Exception("No valid terminal state found");
      Console.WriteLine("Best state {0} and score {1}", beststate, bestscore);
      List<int> best = new List<int>();
      while (beststate != -1)
      {
        best.Add(beststate);
        beststate = tb[beststate];
      }

      return best;
    }

    static void Main(string[] args)
    {
      Graph g = new Graph();
      String input = "ABBCAD";      
      for (int i = 0; i < input.Length - 1; i++)
        for (int j = i + 1; j < input.Length; j++)
        {
          //Modify this of different constraints on-the arcs
          //or graph topologies
          //if (input[i] < input[j])
          g.AddArc(i, j, 1.0f);
        }
      g.SetStart(0);
      //Modify this to make all states final for example
      //To compute longest sub-sequences and so on...
      g.SetFinal(g.NumStates - 1);
      var bestpath = ShortertPath(g);

      //Print the best state sequence in reverse
      foreach (var v in bestpath)
      {
        Console.WriteLine(v);        
      }
    }
  }
}