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?
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?
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.
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.