Jetnor Arifaj

Jetnor Arifaj

  • NA
  • 1
  • 1.6k

Shortest path in an undirected and complete graph

Aug 25 2012 9:06 PM
Hi guys, 
I am stuck in this problem and I hope someone with better knowledge can help. I have asked this question in other forums as nobody is replying.

I have a question which may be very simple but when deadline is looming the brain stops working so there goes:

I have an undirected complete graph with N nodes in it. I have a starting node and I have the distance matrix from each node to the other nodes. I want to run Dijkstra's algorithm or any other algorithm that would work to find the shortest way of visiting all the nodes from the starting node. I want to visit each node only once. I believe the fact that it is a complete graph where each node is connected to the others would make the problem much easier but I cannot wrap my head around coding it. I am using C#. I have already asked another question earlier but this was at an earlier stage where I didn't know much about the problem. Are there any code snippets or pseudo codes available out there or if anyone could start me out I would be very thankful.

I have been looking at QuickGraph and its documentation and other online sources but I can't figure out what I need to have as parameters to run the algorithm. more precisely I don't understand the below code:
1IVertexAndEdgeListGraph<TVertex, TEdge> graph = ...;
2Func<TEdge, double> edgeCost = e => 1; // constant cost
3TVertex root = ...;
4// compute shortest paths
5TryFunc<TVertex, TEdge> tryGetPaths = graph.ShortestPathDijkstra(edgeCost, root);

The above code snippet was taken from: http://quickgraph.co...tance%20Example
if anybody with experience in quickgraph could explain it to me in simple terms what I need to have to make use the below functions that would save me.

To explain what I have is I have a list of Points (x,y) from which I want to build a graph but only showing the edges of the shortest path.