Null endVertex for DijkstraShortestPath?

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Null endVertex for DijkstraShortestPath?

James DeMichele
Hello there,

I had a question about the implementation of DijkstraShortestPath. It appears from the code that an endVertex is required. However, I was hoping that I could use Dijkstra's without giving it an end vertex. The idea being that i want to give it a startVertex and then have it return to me the shortest path that traverses all nodes. The idea being that I'd want to find the shortest path from each starting vertex.

Let me know if this is possible with JGraphT. Thanks!

-JamesD

------------------------------------------------------------------------------
Find and fix application performance issues faster with Applications Manager
Applications Manager provides deep performance insights into multiple tiers of
your business applications. It resolves application problems quickly and
reduces your MTTR. Get your free trial!
https://ad.doubleclick.net/ddm/clk/302982198;130105516;z
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|

Re: Null endVertex for DijkstraShortestPath?

Joris Kinable
Hi James,

I'm not sure I understand what you want. Do you want to compute a shortest path from a specific starting vertex to any other vertex? If so, there are several ways to do this:
1. for each vertex v2 different from your starting vertex v1, invoke dijkstra(v1, v2).
2. you can also use a breath-first-search to do this, which is more efficient.
3. if you want to compute all shortest paths in the graph, i.e. calculate the shortest path in between every pair of vertices, use the FloydWarshall implementations.

"The shortest path that traverses all nodes". That sounds like you want to solve a traveling salesman problem? This problem is NP-hard and there's no exact implementation for that in JGraphT.

br,

Joris

On Fri, May 6, 2016 at 11:48 PM, James DeMichele <[hidden email]> wrote:
Hello there,

I had a question about the implementation of DijkstraShortestPath. It appears from the code that an endVertex is required. However, I was hoping that I could use Dijkstra's without giving it an end vertex. The idea being that i want to give it a startVertex and then have it return to me the shortest path that traverses all nodes. The idea being that I'd want to find the shortest path from each starting vertex.

Let me know if this is possible with JGraphT. Thanks!

-JamesD

------------------------------------------------------------------------------
Find and fix application performance issues faster with Applications Manager
Applications Manager provides deep performance insights into multiple tiers of
your business applications. It resolves application problems quickly and
reduces your MTTR. Get your free trial!
https://ad.doubleclick.net/ddm/clk/302982198;130105516;z
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users



------------------------------------------------------------------------------
Find and fix application performance issues faster with Applications Manager
Applications Manager provides deep performance insights into multiple tiers of
your business applications. It resolves application problems quickly and
reduces your MTTR. Get your free trial!
https://ad.doubleclick.net/ddm/clk/302982198;130105516;z
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users