有向非循环图中的最短路径
我得到了一串字符，其中每个后续的字符对都包含一个边。 我的意思是这是字符串：ABBCAD。 字符串的边缘是：
A->B
B->C
A->D
最短路径距离是A-> D
目前的任务是使用上述规则从字符串中建立一个定向非循环图，并找到最终路径盯着结束于终端节点的根节点（在本例中为A标签）。
NJKUUGHBNNJHYAPOYJHNRMNIKAIILFGJSNAICZQRNM
我收集其中一个方法，其任务是使用深度优先搜索算法。
这不是功课...
这是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; }
}
}
对于这个特殊情况，Dijkstra's可以大大简化。 我想像这样的事情可以做到这一点。
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]}] &)]