TechArena Community The shortest path in a directed graph, Dijkstra algorithm

#1
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?
#2
31-03-2009
 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?
#3
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.
#4
31-03-2009
 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.

 Tags: