# algorithms??

Show 80 post(s) from this thread on one page
Page 2 of 2 First 12
• 12-06-2012
en411
Quote:

How many nodes and edges are we talking about?
The number of nodes may vary upto at most of 50.

Quote:

What is the minimum and maximum number of edges connected to a single node?
Basically my network would be taken from the existing features of the city or any area. So the minimum and maximum number of edges connected to a single node is all dependent on the type of network the user is going to provide. No any restriction to the connection to any node.

Quote:

Do you require the optimum (shortest) path, regardless of computation time (usually requiring a distributed algorithm, so you can run it in reasonable time on e.g. a cluster), or are you looking for an algorithm that will yield just a very good path?
I am looking for an algorithm that will yield a comparatively quickest path that would visit all the nodes.
• 12-06-2012
Nominal Animal
So, this is basically vehicle routing, probably needed for a new sat-nav app or something similar; a variant of the traveling purchaser problem, each city or vertex containing a unique article. (Most sat-nav systems designate every intersection as a vertex, so their graphs have much more vertices. In such cases, endpoints and waypoints are those that have the desired unique articles.)

Quote:

Originally Posted by en411
The number of nodes may vary upto at most of 50.

You have a weighted graph (or network) with up to 50 vertices.

The weight of each edge in your graph is either the geographical distance (in which case your graph is also undirected), or the estimated travel time (in which case you might wish to define the graph as directed, so you can have different travel time estimates per direction), depending on whether you are looking for the shortest or quickest route. Since distance in graph theory refers to the number of edges in a path between two vertices, the thing you are minimizing is technically the weight of the path.

I recommend you look up A* search algorithm and Dijkstra's algorithm.
Show 80 post(s) from this thread on one page
Page 2 of 2 First 12