有向无环图的最短路径

这是一份工作 Djikstra's Algorithm . 一旦你建立了一个图形的表示,它应该很容易产生最低成本的遍历。。。因为在你的情况下,似乎所有的路径都有相同的成本(1)。

你可以 look here on CodeProject

你能给我一个伪代码,你的版本的图形表示这个情况?

adjacency matrix 用于表示边。在这种情况下,您可以使用.NET multidimensional array

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; }
    }
}

对于这种特殊情况,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;
}

只是为了记录。这是您的图形示例:

从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]}] &)]

a series 关于实现 A* algorithm 在C#中。A*是Dijkstra算法的一个更一般的例子:如果你的成本估算函数总是返回0,那么它完全等同于Dijkstra。

另一个选择是使用一个图形库,它实现了各种最短路径算法。我以前用过的一个很好的是 QuickGraph here is a page 在解释如何使用Dijkstra算法的文档中。

由于图是非循环的,可以使用Viterbi算法,按照拓扑顺序访问状态并更新前面顶点(状态)的代价。

下面的代码实现了搜索算法和数据结构。根据最初的问题,我不能百分之百确定有效性的定义。但是,修改代码以构造其他拓扑结构并使用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);        
      }
    }
  }
}