Algorithm for routing in chosen vertexes

Question

I want to choose start point,end point and vertexes that i must pass thru and the algorithm should find the shortest path for routing. I have table that stores Routes Id|Name|StoreA|StoreB|Kilometers,where StoreA and StoreB are FKs from Store table.I save data only for one way. Example:in table Routes 1|Lidl-Kaufland|1|2|157 and not for way back, because the distance is same.I'm not sure if I use BidirectionalGraph or UndirectedGraph from QuickGraph library.

For example this Road Network: 1: https://i.sstatic.net/mxcWe.png First i choose this 4 vertexes then i choose the start and the end one. I use QuickGraph 3.6 and the biggest question here is what graph should I use and is there algorithm for my purpose? Thank you all,I hope that i explained everything necessary to answer me.

Answer 1

Definitely sounds like a Travelling Sales Man problem. There are two was to approach this.

1. If you want to prune the graph to a tree where you'd have the minimum total cost for the graph, please try minimum spanning tree algorithms from Prim or Kruskal. This would eventually give you the minimum total cost graph from the existing graph you have.
2. You can try Travelling Salesman algorithm if you want to go through all the nodes in the graph in the minimum time and make it back to the starting node.
3. If this is an actual road network then you might want to use a directed graph, some roads are one way and some are two way. So you cant possibly say you always have the same distance coming back.
4. If you want an out of the box solution, try PostGis, PostGreSql and PgRouting. As you're saving the data in database already, you can help yourself with the algorithms you need out of the box yourself.

Hope this helps.