Dijkstra's Algorithm in LabVIEW

[Greg_S-Video]

Hello BretD

In the case that you are not used to using LabVIEW, please consider the following free online training resources.

Free Online NI LabVIEW Training for Students and Educators in English - Part 1
http://zone.ni.com/wv/app/doc/p/id/wv-2494

Free Online NI LabVIEW Training for Students and Educators in English - Part 2
http://zone.ni.com/wv/app/doc/p/id/wv-2495

LabVIEW (free) Online Training Resources
https://decibel.ni.com/content/docs/DOC-13978

The first two may take some time to go through by they may also save you lots of time in the future.  All the best and keep us posted!

[BretD]

Well I have attached the vi for the dijkstras algorithm. I have been working on a way to record the vertexes traveled through, but it has not been going well. Hopefully someone might have some good suggestions on how to implement that. On a positive note, the program does output the shortest distance to any nodes visited, and the program works with more then just the number of array elements used ( i.e. feel free to make your own diagram larger or smaller than the example loaded). I will also give a short description of the setup. There are two input cluster arrays. The first array has clusters containing 4 elements. The first is the edge value ( or weight, length, distance, w/e u wanna call it), the second is the v1 value ( initiating vertex associated with that edge value), the third is the v2 value (end vertex traveled to), and the fourth is a boolean switch. Simply switch the value on (before running the vi) for all clusters that initiate from the home vertex ( designated "0"). The second array is composed of 3 element clusters. The first values are all of the vertexes that can be visited (i.e. all vertexes except 0), the second values are the initial pathe lenghts (all set to "infinity", essentially any large value), the third is a boolean switch which designates whether that vertex has been visited. The final array will display the vertex values, and the shortest path lengths to them. There is also a simple numerical control which sets what vertex to end on.

Again, any ideas or suggestions are welcome on how to implement the path finder or improve the current program. Thanks!

[DFGray]

One more tip for you that may save you a little time.  Look in to using custom probes on your data wires.  When I used the priority queue I posted the link to earlier to create a LabVIEW wire routing algorithm, I used custom probes to convert my complex data structures to something more visual.  In my case, this was a graphic containing the obstructions and the proposed route through them.  I used the picture control to create the graphic.

Custom probes are one of the more powerful features of LabVIEW, but largely overlooked my many users.

[BretD]

Thank you for your suggestion DFGray, do you have any good links or sites that would have more info on custom probes? I tried looking up some information, but I couldn't find anything that explained it very well. Thank you!

[DFGray]

If you haven't done so, I would start with the LabVIEW help.  Select the Index tab and type "probes, creating custom" to go to the right page.  I don't know of any other nugget or source for generic use of them, although there are many examples of custom probes on these forums.  Their power is the ability to transform the appearance of data to something more useable.  You can also place complex logic in them to halt on almost any situation you can code.  They have some restrictions (e.g. must not halt execution), but most of the limit is your coding skill.

I believe the reason there is not much written is that there is not much to write.  Right-click a wire, select Custom Probe » New..., go through the wizard, then create your code in the template that was just made for you.

If you run into issues, let us know.  Good luck!

[BretD]

Well I have finally got it working. The VI outputs the path length as well as the route to the path. The 2D array shows the paths. Each row is designated for each vertex, so the first row shows the vertexes traveled through to get to vertex 1, and so on and so forth. For certain rows you may notice that a vertex is repeated for instance " 1,3,3,6", which means that the shortest path to 6 is from 0 to 1 to 3 to 6. The 0 got clipped off and the 3 got repeated due to the way I have the program set up. It is a minor nuisance which I plan to try and fix, but it is still easy enough to tell the path. This is an expanded example of the previous one I uploaded. I wanted to verify that my program works for larger problems, not just the small ones. Though needless to say, the example given is not that large, and I still need to make sure that this can be scaled up further. Ideally, I want to remove the front panel inputs, and have the arrays built from reading values from a text file, but one step at a time. If any one has any feedback on how they think this can be better improved upon, please let me know! Also, feel free to use and modify the VI and let me know about the results 😃 thanks for all the help everyone!

[Greg_S-Video]

Hello BretD

Congratulations on completing your project!  Thank you for choosing National Instruments!

[BretD]

Thank you very much, but I am still trying to make it better. I'm not sure if anyone is interested in updates. If not, this will be my last one, but if anyone has any ideas or wants to see my further progress just let me know. I am posting my newest version. The path display has been much improved, and more accurate. I found this out when I tried a larger path diagram, and I noticed it was giving me weird values. I modified the program, and actually made it simpler and more effective. I have attached my newest vi, along with a diagram to show you what exactly it is solving for. I realize it is hard to probably visualize the problem based on the arrays, so I thought I would add the image so you could get a better idea. Again, feel free to give some feedback, I always appreciate it.

[johnsold]

BretD,

I have been following this thread but had nothing to contribute until now.

I looked at your version 5 VI.  Several suggestions: 1. Try to keep the diagram to one screen.  Learn to use subVIs.

2. Avoid coercion dots.  In your VI they probably do no harm but they are an indication that LV is changing things, possibly in ways you did not intend.  Changing all the numeric variables to I32 does not affect the results and eliminates the coercions at indexing inputs.

3. When autoindexing an array going into a for loop, do not also wire to the N terminal.

4. Some description of what each section is doing would be helpful, especially to you when you come back in about six months and need to change something.

5.  Keeping signals lined up across the diagram makes reading it much easier.  For example the 2D array which eventually becomes Shortest Path Array changes "elevation" 25 times while wandering across the diagram.

There are probably simplifications which could be made but I do not understand what each part is doing.

Lynn

[BretD]

Lynn, 

Thank you for all your suggestions. I realize that there are a lot of small things that I overlooked, or added unnecessarily. I have to say I always wondered what those little dots meant, and now I know lol I was going to use subvis (and I prob will end up using them for clarities sake), but I am always making changes and tweaking different things that its much easier ( at least for me) to see the whole program on the screen. I also feel stupid for wiring the N terminal when I'm autoindexing lol I also need to add some labels, which is something I plan to do because you're right; I will never remember what this program even does in 6 months. I agree that the signals should be lined up across the screen, and they were, but I used the diagram clean up tool to make things more compact and neater. Unfortunately, that also shifted everything around, which is why I should keep the diagram neat in the first place lol Again, thank you for your suggestions! I plan to make alot of the changes you were talkin about as well as document the program. Maybe I'll upload the improved version, upon completion, if anyone wants to see it.