使用Dijkstra算法找到最短路径
我需要找到图形的2个顶点之间的最短路径。 我有一个矩阵，其中包含所有权重。 我该怎么做？ 目前，我有以下代码：
private int[] Dijkstra(int start, int end) { bool[] done = new bool[8]; int[] parent = new int[8]; for (int i = 0; i < parent.Length; i++) parent[i] = -1; int[] distances = new int[8]; for (int i = 0; i < distances.Length; i++) distances[i] = int.MaxValue; distances[start] = 0; int current = start; while (!done[current]) { done[current] = true; for (int i = 0; i < 8; i++) { if (graph[current, i] != int.MaxValue) { int dist = graph[current, i] + distances[current]; if (dist < distances[i]) { distances[i] = dist; parent[i] = current; } } } int min = int.MaxValue; for (int i = 0; i < 8; i++) { if (distances[i] < min&&!done[i]) { current = i; min = distances[i]; } } } return parent; } 它工作，但是，但是，我不知道如何让它找到最短的路线，例如1和3之间，并返回路线，如1 => 4 => 2 => 3。
提前致谢。
Djikstra的算法使用父数组来跟踪从开始到结束的最短路径。 你从父[end]开始并按照数组的条目，直到你回来开始。
一些伪代码：
List shortestPath = new List (); int current = end; while( current != start ) { shortestPath.Add( current ); current = parent[current]; } shortestPath.Reverse();
您唯一担心的是您的函数需要担心的是传入的起始值和结束值是否是适当的值（例如，它们是否实际代表图中的顶点）。
到达目标顶点后，您可以使用父矩阵回溯到起始顶点的路径。 类似的东西（鉴于从源到dest的路径）：
void backtrack(int source, int dest, vector &path) { path.push_back(dest); for(int vertex = parent[dest]; vertex != source; vertex = parent[vertex]) path.push_back(vertex); path.push_back(source); }
注意：路径将按相反顺序排列。
试试QuickGraph解决方案： http ： //quickgraph.codeplex.com/ （也可通过NuGet获得）