Write a program in C++ to calculate the shortest-distance path between any two arbitrary nodes. The edge between any two nodes indicates there is a direct connection between the two nodes. The nodes can be represented by chars or integers reperesented as chars. The distance between any two adjacent nodes (2 nodes with an edge) is an integer number >= 1.
The input must be read from an input text file. Each line of text has three pieces of information that correspond to an edge in the graph and the length (weight) of the edge (distance between 2 nodes).
An input file example (source dest weight) :
1 2 3
2 4 6
10 10 1
etc, etc, etc...
or it can be even easier if you let me just put in the adjaceny matrix like this, (I made this using Matlab) inside a text file:
0,2,6,0,0,0
0,0,3,6,0,0
0,1,0,2,8,0
0,0,0,0,1,8
0,1,0,2,0,1
0,0,0,0,0,0
The second set of input from the user should be to enter any two arbitrary nodes. For example: The input would be d b or 4 2. The output would read: "The shortest path is d e f b" ...." or " 1 2 5 7... The shortest distance is 8" and be in a function call so that this can be called by an external program C++ program with the path returned wether it be a int or char array. Please make the code well commented and compilable on VC++ or g++ w/o modification and that used some sort of log time to run using a heap or stack, but I would be willing to take linear that ran in if it is nice. Something like this in Main would be nice.
main()
{
dijk D
[login to view URL](1,10)
}
It need to be able to compute a rather large input data set ~ 50 nodes and tell me if there isnt a path.
## Deliverables
It is needed by 9AM tommorrow if it can be done that quickly. I can be flexible if someone already has something nice prepackaged with Good Comments.
1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done.
2) Installation package that will install the software (in ready-to-run condition) on the platform(s) specified in this bid request.
3) Exclusive and complete copyrights to all work purchased. (No GPL, 3rd party components, etc. unless all copyright ramifications are explained AND AGREED TO by the buyer on the site).
## Platform
Be able to fun using CV++ 6 or 7 and g++