Dijkstra's Algorithm in LabVIEW

[johnsold]

BretD,

It is a good idea to learn to document as you go along.  It helps you keep track of what you have done.  About the time the program starts working, something will come up which takes you away from it and you never get back to the documentation.  If the documentation is in there before everything works, you cannot create a program without documentation.

Another thing to consider if you change your clusters.  Make them typedefs.  When you change them, the changes propagate to all instances.  That way you do not need to chase around to see how many places you may have used the cluster or a constant derived from it.

SubVIs will help you see what is going on.  Make each subVI perform one task or function.  Give it a descriptive name and icon. Look for code you use more than once - that is a good candidate for a subVI.

Lynn

[BretD]

Unfortunately I have bad habits when it comes to creating VI's which I need to break, but I'm just now starting to really utilize LabVIEW more so it's something I plan on working on.Typedefs is another thing I need to research and try to utilize.

I have updated my program though. I made some minor changes, such as removing unneccessary functions. The main changes are that I added the 4 main functions as sub-vis, each with a lengthy description and an example describing its functionality. I think this make it much easier to see the flow, and understand how the program is broken down. I am uploading this revision so I can get more feedback. Thanks everyone!

[johnsold]

Much nicer.  Please post the subVIs also.  You can zip them to post one file.

Lynn 

[BretD]

Oops, My bad. Here is the zip with the sub-vis as well as the diagram posted earlier.

[BretD]

So more updates! Idk, this thread may be dead, and idk if anyone cares to see my newest update. Here it is anyway though. I've modified the program so that it reads all the info for the shortest path analysis from a simple txt file. The necessary txt file as well as path diagram are included in the zip file. The txt file is set up with a tab delimiter for columns and a carriage return delimeter for rows. Each row contains three values that define each edge. The first column value is the edge weight, the second column value is the V1 value, and the third column value is the V2 value. By looking at the graph and the txt file, you should be able to get an idea of how everything is setup. You can create a txt file and test it for yourself, just don't forget to adjust the final vertex value on the front panel to the correct value, as well as adjusting the "infinity" value to any value larger than any paths. Again, any comments or ideas are always welcome.

[Antares1]

Hello BretD,

I have encountered a small problem with your algorithm. For example, if you have following paths: 01=1,02=9 and 12=1, that is, it's actually using the starting vertex 0. - it will always conclude that 02 is the shortest path from 0 to 2 even if form 0 to 1 the cost is 1 and 0 and from 1 to 2 the cost is also 1., the sum for this path beeing 2.This is displayed correctly in the SPA but the path to 1 is skipped.

Could you please look into this?

Thanks

[BretD]

Hello Antares,

You are absolutely correct. I tried it out and it says incorrectly that from 0-2 is the shortest path, when in fact it should be 0-1-2. I think I know why it is doing that as well. The shortest path vertices are displayed by a sorta lookup table, that appends the shortest path when a new path is found. Unfortunately, the way I have it structured, it automatically assumes that the shortest path to any vertex directly connected to the home vertex is in fact that path. For example in this case, it records 0-2 to be the shortest path because it is connected to the home vertex, despite the fact that the shortest path is through another vertex. I'm probably going to have to redo the logic, but unfortunately I'm trying to finish another project right now so I will not get back to this one til possibly next week. Thank you though for letting me know about the problem.

Thanks!

Bret

[Antares1]

Hi BretD,

I have modified your Path Finder SubVI. I think it works well now.

[2jw288]

How should adjust to parameter?
I don't understand the rule

[Dan_N]

Hi,

What parameter and rule are you referring to? If you mean Dijkstra's Algorithm in general, Wikipedia has a pretty good explanation: http://en.wikipedia.org/wiki/Dijkstra's_algorithm.

Best,

Dan N.

Applications Engineer

National Instruments