c# - 有向无环图中的最短路径

Question

我得到一串字符，其中每对字符都包含一条边。我的意思是这是字符串:ABBCAD。字符串的边缘是:

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

最短路径距离为A->D

手头的任务是使用上述规则从字符串在内存中构建一个有向无环图，并找到从根节点(在给定的示例中为 A 标签)开始到终端节点结束的最短路径。

NJKUUGHBNNJHYAPOYJHNRMNIKAIILFGJSNAICZQRNM

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

这不是作业...

Answer 1

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

您可以 look here on CodeProject在 C# 中合理地实现 Djikstra。

could you present me with a pseudo code of your version of the graph representation for this case?

在这样的问题中，有多种方法可以表示图形。如果图中的顶点数量可能很小 - 使用 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; }
    }
}