Dijkstra's Algorithm in LabVIEW

[BretD]

So I've attempted to undergo the painful task of trying to implement dijkstra's algorithm in LabVIEW. The problem is that I think I am going about doing this wrong, or at least not in the most efficient manner. I've attached my VI so people can take a look at it. I guess I'll also give a brief description of how I'm attempting to implement this. So the input from the user ( at this point) is three 1D arrays as well as a start and end vertex value. The three arrays are the weight values of the edges, V1, and V2. The way these arrays are filled out is so that in each array the coordinating values are all stored at the same index. So if there is a path from vertex 0 to 1, with a weight of 2 then 2 will be stored in the edge array, 0 in the V1 array, and 1 in the V2 array, and all at the same index. These values get fed into functions and the shortest path is found, yada yada yada. I'd explain it more, but I think it'll be easier if you look at the VIs. The problem is that the way I have it setup, creating a finished product to sort through even 20 vertexes would result in massive code. The VI i have is only about 25% complete I'd say, but i dont want to go any further as it is getting exponentially more complicated with each iteration and I feel there has to be a better way. So if anyone has any ideas I would greatly appreciate it!

P.S. I realize that i can write the code in C and call it as a function in the LabVIEW program, but I'm kind of stubborn and want to make this work written solely in LabVIEW

[nathand]

You may want to rethink your data structures; it's hard to follow your arrays.  Consider using an array of clusters.  I wrote some code for a similar project here; it looks for all possible paths and all edges have equal weight, but it might be a useful starting point for you.  It would be easy to add edge weights by making the elements of the "Connections" array into a cluster of a string and a weight, and it would not be too difficult to modify it to allow you to start and end at any arbitrary node.

[BretD]

Awesome! I think that this could definitely help. I am not yet a proficient programmer with LabVIEW, so I haven't ever worked with clusters before, but I think that would definitely help simplify things.

[Greg_S-Video]

Hello BretD

We are thrilled you are using LabVIEW for your application!  Can you please let me know how your implementation using clusters is coming along?  I am committed to helping you resolve this issue.  Please let me know if I can be of any assistane in this regard.  All the best!

[DFGray]

The biggest issue for this algorithm is the priority queue.  I posted an example of a LabVIEW implementation here.  I have used it in both A* and Dijkstra's algorithms.

Good Luck!  You can certainly do this in LabVIEW.

[BretD]

Well I have restarted from scratch and making some good head way I think. Using clusters has made the wiring much less obnoxious and complicated. I've also implemented for loops and conditional loops to cut down on redundant code that I was using in my first attempt. I hope to finish this project by the end of the week, and I'll post it here so everyone can take a look and offer any suggestions. I also want to know more about this priority queue. I've never worked with algorithms before, and I'm not a CS major so I'm trying to pick this stuff up as I go. I read about priority queues and binary heaps and all this when I was doing research on Dijkstra's algorithm, but I haven't found any info on how it is implemented. I understand it ranks a set of values, but I'm not really sure where or how to use it. I assume it's used to rank the path lengths and to pick the smallest one.I think I'm pretty close to implementing the algorithm without one though, but I'm sure in terms of speed and efficiency, my program will be lacking. This isn't necessarily a huge issue to me, as the program isn't going to be used for any sort of high speed demanding application. Thank you everyone for your help! and if anyone has any good links or info that would help me, I'd greatly appreciate it. Thank you!

[CMal]

Bret,

It is worth pointing out that the LabVIEW Robotics module includes an implementation of A* to perform path planning.  If you have access to this module you might be able to use these A* VIs.

Chris M

[Greg_S-Video]

Hello BretD

Since I've written implementations of the Dijstra algorithm in other languages befores, I was wondering which reference you are using for the algorithm.  Do you have a textbook reference?  I'm really interested to know.  Do you have a state transition diagram?  I'd be really interested to see your planning for this implementation!  (Projects like these are exciting to me!)  Please see the following link:

LabVIEW Core 1 - The Software Development Method

http://zone.ni.com/devzone/cda/tut/p/id/10051

Thank you very much for your effort and we appreciate your contribution to the LabVIEW community!

[BretD]

Well I'm glad that there are others interested in this project. First I'd just like to give a little update. The program currently will give the length of the shortest path to the desired vertex, but it doesn't output what the path it took to get that shortest value yet. So that is what I am working on now, as well as verifying its scalability and trying to implement other features that will actually make this a useful program vs. mere curiosity. 

As far as my references go, I've gotten all my info from the internet. Wikipedia, of course, was my starting place. I found a well explained article at http://eoinbailey.com/blog/dijkstras-algorithm-illustrated-explanation that helped me decide how I was going to try and implement the program. I also read pretty much the rest of the links that come up on google when you type in "dijkstras algorithm." Again, I have no formal CS background, Im studying engineering, so I'm working with a lot of trial and error here. My basic methodology behind all this was simply to read as much as I could, try to understand it, and then work on the program until I started getting somewhere. Maybe not the best strategy, but it works for me. Thank you also for the link, I wish I had read that before I had started this project lol

I will post my latest version of the VI later today, This way I can get some feedback on how I can improve it and what works or doesn't work. Thanks again everyone for all ur help!

[BretD]

Thanks chris for your suggestion. Unfortunately I do not have access to that module, and after looking at that price I dont think I ever will lol ( I use LabVIEW at my university, so I just use whatever they got). I also want to finish making it myself now, just so I can say i did it, but thank you though!