Trying to follow the example listed here: QuickGraph Dijkstra example. I had to change some to of the code to get it to work, not sure if the example was out of date. '''
using QuickGraph;
using QuickGraph.Algorithms;
using QuickGraph.Algorithms.Observers;
using QuickGraph.Algorithms.ShortestPath;
namespace Markov
{
internal class Program
{
private static void Main(string[] args)
{
AdjacencyGraph<string, Edge<string>> graph = new AdjacencyGraph<string, Edge<string>>(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<string> a_b = new Edge<string>("A", "B");
Edge<string> a_d = new Edge<string>("A", "D");
Edge<string> b_a = new Edge<string>("B", "A");
Edge<string> b_c = new Edge<string>("B", "C");
Edge<string> b_e = new Edge<string>("B", "E");
Edge<string> c_b = new Edge<string>("C", "B");
Edge<string> c_f = new Edge<string>("C", "F");
Edge<string> c_j = new Edge<string>("C", "J");
Edge<string> d_e = new Edge<string>("D", "E");
Edge<string> d_g = new Edge<string>("D", "G");
Edge<string> e_d = new Edge<string>("E", "D");
Edge<string> e_f = new Edge<string>("E", "F");
Edge<string> e_h = new Edge<string>("E", "H");
Edge<string> f_i = new Edge<string>("F", "I");
Edge<string> f_j = new Edge<string>("F", "J");
Edge<string> g_d = new Edge<string>("G", "D");
Edge<string> g_h = new Edge<string>("G", "H");
Edge<string> h_g = new Edge<string>("H", "G");
Edge<string> h_i = new Edge<string>("H", "I");
Edge<string> i_f = new Edge<string>("I", "F");
Edge<string> i_j = new Edge<string>("I", "J");
Edge<string> i_h = new Edge<string>("I", "H");
Edge<string> j_f = new Edge<string>("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
//Because the algorithm takes a delegate as the edge cost, one cannot simply pass a dictionary. QuikGraph provides an helper method, GetIndexer, to make the conversion
Dictionary<Edge<string>, double> edgeCostDict = new Dictionary<Edge<string>, double>();
edgeCostDict.Add(a_b, 4);
edgeCostDict.Add(a_d, 1);
edgeCostDict.Add(b_a, 74);
edgeCostDict.Add(b_c, 2);
edgeCostDict.Add(b_e, 12);
edgeCostDict.Add(c_b, 12);
edgeCostDict.Add(c_f, 74);
edgeCostDict.Add(c_j, 12);
edgeCostDict.Add(d_e, 32);
edgeCostDict.Add(d_g, 22);
edgeCostDict.Add(e_d, 66);
edgeCostDict.Add(e_f, 76);
edgeCostDict.Add(e_h, 33);
edgeCostDict.Add(f_i, 11);
edgeCostDict.Add(f_j, 21);
edgeCostDict.Add(g_d, 12);
edgeCostDict.Add(g_h, 10);
edgeCostDict.Add(h_g, 2);
edgeCostDict.Add(h_i, 72);
edgeCostDict.Add(i_f, 31);
edgeCostDict.Add(i_h, 18);
edgeCostDict.Add(i_j, 7);
edgeCostDict.Add(j_f, 8);
Func<Edge<string>, double> edgeCost = AlgorithmExtensions.GetIndexer(edgeCostDict);
// We want to use Dijkstra on this graph
DijkstraShortestPathAlgorithm<string, Edge<string>> dijkstra = new DijkstraShortestPathAlgorithm<string, Edge<string>>(graph, edgeCost);
// attach a distance observer to give us the shortest path distances
VertexDistanceRecorderObserver<string, Edge<string>> distObserver = new VertexDistanceRecorderObserver<string, Edge<string>>(edgeCost);
distObserver.Attach(dijkstra);
// Attach a Vertex Predecessor Recorder Observer to give us the paths
VertexPredecessorRecorderObserver<string, Edge<string>> predecessorObserver = new VertexPredecessorRecorderObserver<string, Edge<string>>();
predecessorObserver.Attach(dijkstra);
// Run the algorithm with A set to be the source
dijkstra.Compute("A");
foreach (KeyValuePair<string, double> kvp in distObserver.Distances)
Console.WriteLine("Distance from root (A) to node {0} is {1}", kvp.Key, kvp.Value);
foreach (KeyValuePair<string, Edge<string>> 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);
PrintShortestPath("A", "H", graph, edgeCost);
}
private static void PrintShortestPath(string @from, string to, AdjacencyGraph<string, Edge<string>> graph, Func<Edge<string>, double> edgeCost)
{
var tryGetPath = graph.ShortestPathsDijkstra(edgeCost, @from);
//var pathDistance = graph.
IEnumerable<Edge<string>> path;
if (tryGetPath(to, out path))
{
foreach (var item in path)
{
Console.WriteLine($"{@from}, {to}, {item}");
}
}
else
{
Console.WriteLine($"No path found from {@from} to {to}.");
}
}
}
}
'''
The Function ShortestPathsDijkstra provides the path, but is there a way to follow the cost along with the path? Print out 1 ,22, 10?
