0

I found this algorithm that is WAY beyond my comprehension and JS skills. https://rosettacode.org/wiki/Dijkstra%27s_algorithm#JavaScript Somehow I managed to use it a few months ago for a musical application I'm working on.

It works great... but I realized a while ago that this implementation returns only one of the possible shortest paths between two nodes.

For instance in this graph :

enter image description here

the shortest path between k->g can be either through h, i or j

[EDIT : in that case all my weights are equal to 1, but I do use weights in my system with more complex graphs. I just needed a very simple example to explain...]

So far I managed to retrieve this kind of alternatives by randomizing the graph (I don't even understand how it worked...), to get varying destinations when exploring it, but this is far from convenient. It will become heavier when dealing with bigger graphs, and in any case I just realized I need the full list of smallest paths for higher-level calculations I'm making in my system.

Does anyone have an idea of how I could modify this code to get all possibilities? I found similar links on stackoverflow but with different implementations or languages that I really don't know at all.

Any help will be much appreciated ! Thanks

Julien

Julien Vincenot
  • 101
  • 5
  • `I found similar links on stackoverflow but with different implementations or languages` - such as? show the links you've found (at least it shows you've done some research) – Bravo Oct 16 '19 at 03:51
  • indeed : like this one (I guess it's similar but I don't know Java) https://stackoverflow.com/questions/50411987/using-dijkstra-to-detect-multiple-shortest-paths – Julien Vincenot Oct 16 '19 at 03:52
  • or this one : https://stackoverflow.com/questions/2819347/dijkstras-algorithm-to-find-all-the-shortest-paths-possible#_=_ – Julien Vincenot Oct 16 '19 at 03:54
  • @JulienVincenot The shortest paths from *k* to *g* is not necessarily those you said, **shortest** means *a path with least cumulative weight* and **not** a path with least amount of nodes in between. Before dwelling into implementations you should get a deeper understanding of it. – Javier Silva Ortíz Oct 16 '19 at 03:58
  • Seems like you're working on an undirected unweighted graph. If that is the case, you can just do a BFS. I also don't know what you mean by a "full list of shortest paths". If that means paths from any node to any other node, that would take up a lot of space (`|V| choose 2` lists to be precise) – slider Oct 16 '19 at 04:05
  • @JavierSilvaOrtíz : indeed, during editing I removed the actual text of my graph showing the weights. They are all equal to 1 in that VERY simple example. I do understand very BASIC graph theory thank you. – Julien Vincenot Oct 16 '19 at 04:05
  • @slider sorry, indeed my graphs are undirected by they do have weights. As I said I managed to use the code for months, I just don't know how to modify it to have more flexibility. – Julien Vincenot Oct 16 '19 at 04:06
  • @JulienVincenot What you need is a common variation of Dijkstra's known as a *shortest path tree*. Since you're already familiar with the theory you can check https://en.wikipedia.org/wiki/Shortest-path_tree for pseudo code. – Javier Silva Ortíz Oct 16 '19 at 04:19
  • @JavierSilvaOrtíz thank you but I don't understand this pseudocode. I was serious when I meant VERY BASIC understanding, meaning I understand how to "play" with it. As I said I'm a musician not a professional coder, I need this for a much bigger project that I built with a visual programming interface (MaxMSP) that has an interface with JS. I don't use JS because I want to, I'm using it because the code exists and I needed it. This algorithm is a very small brick I don't understand but when it works I'm able to keep working on my music which happens in the MaxMSP patch, not in in JS. – Julien Vincenot Oct 16 '19 at 04:37
  • How many nodes/paths are you dealing with? – Bravo Oct 16 '19 at 04:45
  • Wow thanks both ! My graphs are not limited yet but I basically write them by hand, so I guess between 50 and 200 nodes each. Connectivity / topology can vary a lot, as I use it to produce different rhythmic effects. Probably I'll hold my horses if I realize it's to heavy to compute, it's supposed to run live on my laptop... – Julien Vincenot Oct 16 '19 at 04:50

1 Answers1

0

ok so this is very far from elegant but a good enough solution I found is, instead of modifying the algorithm itself (which still feels like Everest to me even though I spent the whole night studying the code in depth !) :

1) run the algorithm several times with the same variables except :

2) everytime the graph list is rotated by a single step

[[a, b, 1],[b, c, 1],[c, a, 1]]
[[b, c, 1],[c, a, 1],[a, b, 1]]
[[c, a, 1],[a, b, 1],[b, c, 1]]

... and more for bigger graphs

3) same thing but also with reversed graph

[[c, a, 1],[b, c, 1],[a, b, 1]]
[[b, c, 1],[a, b, 1],[c, a, 1]] 
[[a, b, 1],[c, a, 1],[b, c, 1]]

... same

4) collecting all of those solutions, then removing duplicates.

This seems to work because the Dijkstra scans through the graph list step by step to build its solution, so first come first serve I guess...

That way I get all the shortest paths I want, except in one single case : when weights are not equal in "equivalent segments" between two nodes — by equivalent I mean same number of nodes between them.

This forces me to evaluate the code on both the weighted graph and an unweighted copy when I just need all possible paths between some highly connected nodes, but this is totally manageable for what I need and considering the modest size of my graphs...

Thanks everyone for your suggestions ! Best,

Julien

Julien Vincenot
  • 101
  • 5