1

I implemented a C# Dijkstra with Fibonacci Heap using based on SO question and this version in Java, which is very clean, concise and well documented.

I modified the DirectedGraph to make it an undirected graph.

However, I have 2 questions regarding the search algorithm itself:

  1. The current method has 2 parameters (graph & source). If I add a third parameter (target), what are the changes necessary in the search algorithm itself so that it only searches from source to target instead of all-pairs shortest paths?

  2. The function returns a list of distances. What do I need to change to make it return the shortest path?

2
  • I don't understand the first question, but #2 as the list of distances the shortest path is the list with the lowest count, or you mean you only want it to return one path without checking the other paths? via weights?.
    – Xela
    May 23, 2016 at 4:27
  • @Xela Usually, when using Dijkstra the nodes making up the shortest path are added to a list, with the target node being the first entry. Then to get the shortest path one backtracks this list. But the current implementation just has a result variable that contains all nodes, some with weights and most others with +infinity. May 23, 2016 at 6:24

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.