QuickGraph Dijkstra的例子

我有一个AdjacencyGraph>我想要运行AlgorithmExtensions.ShortestPathsDijkstra的,但QuickGraph文档并不是最好的.

有没有人有我可以效仿的例子？

我在Google上找到的所有东西都使用了一个观察者,AlgorithmExtension不需要它.

从quickgraph.codeplex.com上获取的关于在QuickGraph上运行Dijkstra算法的示例.

AdjacencyGraph> graph = new AdjacencyGraph>(true);

// Add some vertices to the graph
graph.AddVertex("A");
graph.AddVertex("B");
graph.AddVertex("C");
graph.AddVertex("D");
graph.AddVertex("E");
graph.AddVertex("F");
graph.AddVertex("G");
graph.AddVertex("H");
graph.AddVertex("I");
graph.AddVertex("J");

// Create the edges
Edge a_b = new Edge("A", "B");
Edge a_d = new Edge("A", "D");
Edge b_a = new Edge("B", "A");
Edge b_c = new Edge("B", "C");
Edge b_e = new Edge("B", "E");
Edge c_b = new Edge("C", "B");
Edge c_f = new Edge("C", "F");
Edge c_j = new Edge("C", "J");
Edge d_e = new Edge("D", "E");
Edge d_g = new Edge("D", "G");
Edge e_d = new Edge("E", "D");
Edge e_f = new Edge("E", "F");
Edge e_h = new Edge("E", "H");
Edge f_i = new Edge("F", "I");
Edge f_j = new Edge("F", "J");
Edge g_d = new Edge("G", "D");
Edge g_h = new Edge("G", "H");
Edge h_g = new Edge("H", "G");
Edge h_i = new Edge("H", "I");
Edge i_f = new Edge("I", "F");
Edge i_j = new Edge("I", "J");
Edge i_h = new Edge("I", "H");
Edge j_f = new Edge("J", "F");

// Add the edges
graph.AddEdge(a_b);
graph.AddEdge(a_d);
graph.AddEdge(b_a);
graph.AddEdge(b_c);
graph.AddEdge(b_e);
graph.AddEdge(c_b);
graph.AddEdge(c_f);
graph.AddEdge(c_j);
graph.AddEdge(d_e);
graph.AddEdge(d_g);
graph.AddEdge(e_d);
graph.AddEdge(e_f);
graph.AddEdge(e_h);
graph.AddEdge(f_i);
graph.AddEdge(f_j);
graph.AddEdge(g_d);
graph.AddEdge(g_h);
graph.AddEdge(h_g);
graph.AddEdge(h_i);
graph.AddEdge(i_f);
graph.AddEdge(i_h);
graph.AddEdge(i_j);
graph.AddEdge(j_f);

// Define some weights to the edges
Dictionary, double> edgeCost = new Dictionary, double>(graph.EdgeCount);
edgeCost.Add(a_b, 4);
edgeCost.Add(a_d, 1);
edgeCost.Add(b_a, 74);
edgeCost.Add(b_c, 2);
edgeCost.Add(b_e, 12);
edgeCost.Add(c_b, 12);
edgeCost.Add(c_f, 74);
edgeCost.Add(c_j, 12);
edgeCost.Add(d_e, 32);
edgeCost.Add(d_g, 22);
edgeCost.Add(e_d, 66);
edgeCost.Add(e_f, 76);
edgeCost.Add(e_h, 33);
edgeCost.Add(f_i, 11);
edgeCost.Add(f_j, 21);
edgeCost.Add(g_d, 12);
edgeCost.Add(g_h, 10);
edgeCost.Add(h_g, 2);
edgeCost.Add(h_i, 72);
edgeCost.Add(i_f, 31);
edgeCost.Add(i_h, 18);
edgeCost.Add(i_j, 7);
edgeCost.Add(j_f, 8);

// We want to use Dijkstra on this graph
DijkstraShortestPathAlgorithm> dijkstra = new DijkstraShortestPathAlgorithm>(graph, edgeCost);

// attach a distance observer to give us the shortest path distances
VertexDistanceRecorderObserver> distObserver = new VertexDistanceRecorderObserver>();
distObserver.Attach(dijkstra);

// Attach a Vertex Predecessor Recorder Observer to give us the paths
VertexPredecessorRecorderObserver> predecessorObserver = new VertexPredecessorRecorderObserver>();
predecessorObserver.Attach(dijkstra);

// Run the algorithm with A set to be the source
dijkstra.Compute("A");

foreach (KeyValuePair kvp in distObserver.Distances)
Console.WriteLine("Distance from root to node {0} is {1}", kvp.Key, kvp.Value);

foreach(KeyValuePair> kvp in predecessorObserver.VertexPredecessors)
Console.WriteLine("If you want to get to {0} you have to enter through the in edge {1}", kvp.Key, kvp.Value );

// Remember to detach the observers
distObserver.Detach(dijkstra);
predecessorObserver.Detach(dijkstra);

我已经更新了文档,但简而言之,您需要一个图形,一个边权重图(作为委托)和一个根顶点.AlgorithmExtensions方法返回一个'TryFunc',您可以查询它以获取最短路径.

using QuickGraph;
using QuickGraph.Algorithms;

IVertexAndEdgeListGraph graph = ...;
Func edgeCost = e => 1; // constant cost
TVertex root = ...;

// compute shortest paths
TryFunc tryGetPaths = graph.ShortestPathDijkstra(edgeCost, root);

// query path for given vertices
TVertex target = ...;
IEnumerable path;
if (tryGetPaths(target, out path))
    foreach(var edge in path)
        Console.WriteLine(edge);