Akdora’s Blog

Programming, Oracle, Life, Fun

Dijkstra’s Algorithm Example in C January 10, 2007

Filed under: C & C++ — Akdora @ 5:56 pm
Tags: , , , ,

In this assignment, you will help a transportation company. There will be a main office of the company and a number of branch offices. The main office wants to deliver some goods to other offices, so for each branch, a truck goes out from main office. Company knows the distances between the offices and wants to use the shortest path toward each office to reduce their costs. Your program will find the shortest paths from main office to each branch offices.

1.JPG

Your program will read the number of offices and the distance matrix from a text file as in he following sample input file.

2.JPG

First row indicates the distance from 0th office to offices 0,1,2,3,4, respectively. Second row similarly indicates the distance from 1st office to offices 0,1,2,3,4, respectively and so forth. If there is a connection from x to y with a distance of d> 0 then you should set M[x][y] = d If there is no connection, -1 is provided as an entry, then M[x][y] = -1
Main office
Everyone will use his/her university id number’s first 2 and last 3 digits as the seed for the random number generator. If your id is 990702003 then you will use 99003 as the seed. Random number generator will decide which office will be considered as the main office and your algorithm will execute accordingly.
Output File
Example: Main office is randomly determined as “0”, then following output file must be generated:

3.JPG

Solution :

input.txt
output.txt
solution in c

 

22 Responses to “Dijkstra’s Algorithm Example in C”

  1. vinay Says:

    hi,
    i want to know the difference in coding between the calculation of the shortest path and the quickest path using dijikstra s algorithm.
    I think the shortest path is based on the weights only where as quickest path depends on both the (sum of the delays + data/capacity)

    please help me with this I NEED to write a code in C /C++
    Thank you,
    vinay

  2. akdora Says:

    I wrote the code for the shortest path for my homework.. At the beginnig, Code give every distance between nodes an infinite number.Then try to reach the shortest way.. I never heard about quickest path.. I am sorry I cannot help you. you may keep searching this.

  3. akdora Says:

    There is a bug for the paths in the code.. Then I send another code..
    https://akdora.files.wordpress.com/2007/03/dijkstraexample_by_char.c

  4. sudha Says:

    hi!!
    i wld like to receive c/c++ code for cryptographic knapsack problem.
    can anybody help out wit this..

    have a nice day
    tke care

    Sudha

  5. sudha Says:

    hey sorry ..!! posted a question at the comment section..

  6. protocol Says:

    There is still bug in this code with memory allocation. MALLOC2D macro is called with wrong data type. PATHS type int**.
    PATHS = MALLOC2D( int , vertexNum );
    There will be no problem in this case because sizeof(int)=4 which is the unit length of any pointer. But
    ROUTE = MALLOC2D( char , vertexNum );
    This is a mistake. because ROUTE type is char** and the sizeof(char) is one.

    The fix is change the MALLOC2D macro like this: #define MALLOC2D(t,n) (t*) malloc( n*sizeof(t) )

    And allocate ROUTE and PATHS like:
    PATHS = MALLOC2D( int* , vertexNum );
    ROUTE = MALLOC2D( char , vertexNum );

    Program output is also wrong: I get the following output:which are different from the one which is given here.

    Nodes Path Distance
    ——————————
    2 – 0 2-4-0 11
    2 – 1 No conn 999999999
    2 – 3 No conn 999999999
    2 – 4 2-4 4

    It would be nice to get working code otherwise it makes people confusing rather helping.

  7. subhajit dutta Says:

    i want a C code for wireless mobile technology by dijkstra algo. and i also want the C code in that where when a node is failure to send data to its destination node , then how the other node, who is sending data, select the another node to send data , by the criteria of the nodes waitage, charge,& shortest path. please give me the C code for when a node is out of the range of its circle, then how the source node find the shortest path. i m clearly saying that i want the C code of wireless mobile technology…………………

    anybody please help me………………………..

  8. onyemaechi Says:

    please am doing a school assignment on improved dijkstra algorithm simulation using matlab. could you send me the complete source code of the simulation. this will be of great help.thanks

  9. kel Says:

    Hi vinay, not sure if u can c this but i am pretty curious abt ur first posting regarding the fastest path. Have u any updates on this yet???

  10. chihntan Says:

    Task: Given a topology and a certain node X, find the shortest path tree with X as the root.====================================================================== * Input: a topology file similar to the following (which is a three-node ring) ——————————————–Nodes: (3) // there are three nodes (node 0, 1 and 2) Edges: (3)ID node node cost0 0 1 100 // there is an bidirectional edge between node 0 & 1, the edge ID is 0, and the cost is 1001 1 2 502 2 0 100——————————————– * Output: Description of the tree as following, the order should be based on breadth-first search0(0) 1(0) 2(0) where A(B) means the parent of node A is node B * Requirements:- Use standard C++- Use of Dijkstra’s algorithm is required when finding shortest paths- Your code MUST be written by yourself. Copying is not allowed.- No GUI- Platform independent (can be compile under both Windows and Linux)- The code must be compilable- Use of STL is recommended (but not required)- Use of class is required

  11. lui Says:

    help me. i m a beginner. want code for shortest path and its weight.

  12. Hey, nice tips. I’ll buy a glass of beer to that person from that forum who told me to go to your blog🙂

  13. Joao Says:

    Hi. I tested your Dijkstra code with the following data and an error occurred. Did I do something wrong?
    10
    0 4 -1 8 11 -1 -1 -1 -1 -1
    4 0 17 -1 14 -1 -1 -1 -1 -1
    -1 17 0 -1 13 3 -1 -1 -1 -1
    8 -1 -1 0 13 -1 7 9 -1 -1
    11 14 13 13 0 5 -1 10 -1 -1
    -1 -1 3 -1 5 0 -1 6 12 -1
    -1 -1 -1 7 -1 -1 0 12 -1 11
    -1 -1 -1 9 10 6 12 0 2 9
    -1 -1 -1 -1 -1 12 -1 2 0 10
    -1 -1 -1 -1 -1 -1 11 9 10 0

    Nevertheless, great code.
    Joao

  14. Very nice article I like your blog carry on the amazing posts

  15. vanusha Says:

    i too tested, this coding got a wrong output

  16. mouli Says:

    please striaght meaning of dijkstra algorithm in c program

  17. i tried akdora.wordpress.com in the past and i like it, just keep it up!

    i am sorry if i wrote in wrong section and please admins to move this to another place.

    i am find ways to make money on the net. what posibilities we have? have you ever tried survey sites? i
    t seems to be easy to make money. i found myhotrevenue dot com in my searches. IS this legit? anyone know?

  18. temporary Says:

    please code it!

  19. satish.m Says:

    i need some c code for finding shortest path for particular two nodes please help me i am doing national project

  20. Great post but I was wanting to know if you could write a litte more on this subject? I’d be very thankful if you could elaborate a little bit more. Kudos!

  21. unable to access the input.txt file

  22. ttt Says:

    i dont like this coding very very dfclt


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s