algorithms??

This is a discussion on algorithms?? within the Tech Board forums, part of the Community Boards category; How many nodes and edges are we talking about? The number of nodes may vary upto at most of 50. ...

  1. #16
    Registered User
    Join Date
    Sep 2012
    Posts
    8
    How many nodes and edges are we talking about?
    The number of nodes may vary upto at most of 50.

    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.

    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.

  2. #17
    Registered User
    Join Date
    Oct 2011
    Posts
    847
    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 View Post
    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.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Algorithms
    By samtay in forum C++ Programming
    Replies: 2
    Last Post: 03-08-2004, 12:14 PM
  2. STL algorithms
    By PJYelton in forum C++ Programming
    Replies: 7
    Last Post: 11-12-2002, 02:27 PM
  3. any more algorithms ?
    By black in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 07-31-2002, 01:00 AM
  4. C Algorithms
    By Garfield in forum C Programming
    Replies: 2
    Last Post: 09-28-2001, 02:59 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21