Go Back   TechArena Community > Software > Software Development
Become a Member!
Forgot your username/password?
Tags Active Topics RSS Search Mark Forums Read

Reply
 
Thread Tools Search this Thread
  #1  
Old 31-03-2009
Member
 
Join Date: Feb 2008
Posts: 324
The shortest path in a directed graph, Dijkstra algorithm

I'm looking for a java algorithm to find the shortest path in a directed graph from the vertex 1 to vertex n and through k vertices. This last condition that I have a problem. I thought of course use the Dijkstra algorithm. What do you think? And how to modify it to pass through k vertices?
Reply With Quote
  #2  
Old 31-03-2009
XSI XSI is offline
Member
 
Join Date: May 2008
Posts: 271
Re: The shortest path in a directed graph, Dijkstra algorithm

When you say "going through k vertices," you mean that you are looking for a path from a vertex of v and going to another vertex of x and size at least k, or from v to x and passing through at least each vertex of a K?
Reply With Quote
  #3  
Old 31-03-2009
Member
 
Join Date: Feb 2008
Posts: 324
Re: The shortest path in a directed graph, Dijkstra algorithm

I want to find the path from the vertex s to vertex t and through k distinct vertices. That is, it must impose an exact number of k vertices.
Reply With Quote
  #4  
Old 31-03-2009
XSI XSI is offline
Member
 
Join Date: May 2008
Posts: 271
Re: The shortest path in a directed graph, Dijkstra algorithm

In this case, make a journey of your graph in Dijkstra and instead store the shortest path for each vertex, remember all the paths leading to the vertex with their length in terms of distinct nodes.
Reply With Quote
Reply

  TechArena Community > Software > Software Development
Tags: , , ,



Thread Tools Search this Thread
Search this Thread:

Advanced Search


Similar Threads for: "The shortest path in a directed graph, Dijkstra algorithm"
Thread Thread Starter Forum Replies Last Post
Adobe reader close by DEP when directed to print Yogisa Windows Software 4 16-09-2011 12:09 AM
SandyBridge mainboard support Intel VT-d Technology Directed I/O Lyudmyla Motherboard Processor & RAM 6 16-07-2011 10:18 AM
Keep being directed to random sites from google such as adcloudmedia.com miketaylor05 Windows Software 6 04-06-2010 12:15 AM
Change Default Windows Installation Path to Your Desired Path phones Tips & Tweaks 0 23-03-2009 11:32 PM
Open Shortest Path First and Integrated Services Digital Network backup Fenton Networking & Security 3 11-11-2008 06:19 PM


All times are GMT +5.5. The time now is 10:15 AM.