有向无环图中的最短路径

Question

我被赋予了一串字符,其中每个随后的一对字符都包含一个边.我的意思是这是字符串:ABBCAD.字符串的边缘是:

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

最短路径距离为A-> D.

手头的任务是使用上述规则从字符串构建内存中的有向非循环图,并找到在终端节点处结束的根节点(在示例中给出它的A标签)的最短路径.

NJKUUGHBNNJHYAPOYJHNRMNIKAIILFGJSNAICZQRNM

我收集的任务之一就是使用Depth First Search算法.

这不是作业......

Answer 1

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

您可以在这里查看CodeProject,以便在C#中合理地实现Djikstra.

你能给我一个你的版本的图表表示的伪代码吗？

在这样的问题中有多种表示图形的方法.如果图中顶点的数量可能很小 - 使用邻接矩阵表示边缘就足够了.在这种情况下,您可以使用.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;
}