|
|
#1
05-Jan-2009, 15:42
|
|||
|
|||
Shortest path includes all subsetIn graphs (V,E) with negative edge weights but with no negative cycles , X <V and s, t in V .I need an algorithm to decide if exist in the graph shortest path from s to t with which includes all the nodes from X
i've tried to modify A* , Bellman-Ford algorithms but without success . |
|||
|
#2
05-Jan-2009, 16:15
|
||||
|
||||
Re: shortest path includes all subsetIf I'm understanding what you're asking correctly, the problem you're trying to solve is NP-Complete.
__________________
www.blake-foster.com |
Recent GIDBlog
Once again, no time for hobbies by crystalattice
| Thread Tools | Search this Thread |
| Rate This Thread | |
|
|
Similar Threads
|
||||
| Thread | Thread Starter | Forum | Replies | Last Post |
| Shortest path algorithm with a maximum number of edges limit | blackslither | C++ Forum | 1 | 28-Dec-2008 11:39 |
| Shortest Path for Airport | mxb1145 | C++ Forum | 1 | 16-Dec-2008 07:28 |
| Need Help - Shortest Path Problem | mas287 | C Programming Language | 5 | 18-Jun-2008 03:59 |
| Shortest Path Program. | bomber456 | C++ Forum | 1 | 05-Mar-2007 13:32 |
| shortest path algorithm and file saving | Pandiani | C++ Forum | 10 | 17-Jul-2006 11:46 |
Network Sites: GIDNetwork · GIDWebHosts · GIDSearch · Learning Journal by J de Silva, The
