In this article I describe Dijkstra’s algorithm for finding the shortest path from one source to all the other vertexes in a graph. Afterwards, I provide the source code in C of a simple implementation.

To understand this you should know what a graph is, and how to store one in memory. If in doubt check this and this.

Another solution for this problem is the Bellman-Ford algorithm.

#### The Problem

Given the following graph calculate the length of the shortest path from **node 1** to every other node.

Lets take the nodes **1** and **3**. There are several paths (**1 -> 4 -> 3**, **1 -> 2 -> 3**, etc.), but the shortest of them is **1 -> 4 -> 2 -> 3** of length **9**. Our job is to find it.

#### The Algorithm

Dijkstra’s algorithm is one of the most common solutions to this problem. Even so, it only works on graphs which have **no edges of negative weight**, and the actual speed of the algorithm can vary from **O(n*lg(lg(n)))** to **O(n ^{2})**.

The idea is somewhat simple:

Take the length of the shortest path to all nodes to be infinity. Mark the length of the shortest path to the source as *0*.

Now, we already know that the graph has no edges of negative weight so the a path of length *0* is the best we can come up with. The path to the source is *0*, so it’s optimal.

This algorithm works by making the paths to one more node optimal at each step. So, at the *k*th step, you know for sure that there are at least *k* nodes to which you know the shortest path.

At each step, choose the node, which is not yet optimal, but which is closest to the source; i.e. the node to which the current calculated shortest path is smallest. Then, from it, try to optimise the path to every node connected to it. Finally, mark the said node as *optimal* (visited, if you prefer). In the previous example, the node which is closest to the source and is not yet optimal is the source. From it, you can optimise the path to nodes *2* and *4*.

At this point, the only visited/optimal node is *0*. Now we have to redo this step *4* more times (to ensure that all nodes are optimal).

The next node to consider is *4*:

It’s worthwhile to note that at this step, we’ve also found a better path to node *2*.

Next is node *2*:

Finally, we look at nodes *5* and *3* (none of which offer any optimisations):

The actual code in C looks something like this:

void dijkstra(int s) { int i, k, mini; int visited[GRAPHSIZE]; for (i = 1; i <= n; ++i) { d[i] = INFINITY; visited[i] = 0; /* the i-th element has not yet been visited */ } d[s] = 0; for (k = 1; k <= n; ++k) { mini = -1; for (i = 1; i <= n; ++i) if (!visited[i] && ((mini == -1) || (d[i] < d[mini]))) mini = i; visited[mini] = 1; for (i = 1; i <= n; ++i) if (dist[mini][i]) if (d[mini] + dist[mini][i] < d[i]) d[i] = d[mini] + dist[mini][i]; } } [/sourcecode] <h4>The Programme</h4> Putting the above into context, we get the <strong>O(n<sup>2</sup>)</strong> implementation. This works well for most graphs (it will <strong>not</strong> work for graphs with negative weight edges), and it's quite fast. Here's the source code in C (<a href='https://compprog.files.wordpress.com/2007/12/dijkstra.c' title='dijkstra.c'>dijkstra.c</a>): #include <stdio.h> #define GRAPHSIZE 2048 #define INFINITY GRAPHSIZE*GRAPHSIZE #define MAX(a, b) ((a > b) ? (a) : (b)) int e; /* The number of nonzero edges in the graph */ int n; /* The number of nodes in the graph */ long dist[GRAPHSIZE][GRAPHSIZE]; /* dist[i][j] is the distance between node i and j; or 0 if there is no direct connection */ long d[GRAPHSIZE]; /* d[i] is the length of the shortest path between the source (s) and node i */ void printD() { int i; for (i = 1; i <= n; ++i) printf("%10d", i); printf("\n"); for (i = 1; i <= n; ++i) { printf("%10ld", d[i]); } printf("\n"); } void dijkstra(int s) { int i, k, mini; int visited[GRAPHSIZE]; for (i = 1; i <= n; ++i) { d[i] = INFINITY; visited[i] = 0; /* the i-th element has not yet been visited */ } d[s] = 0; for (k = 1; k <= n; ++k) { mini = -1; for (i = 1; i <= n; ++i) if (!visited[i] && ((mini == -1) || (d[i] < d[mini]))) mini = i; visited[mini] = 1; for (i = 1; i <= n; ++i) if (dist[mini][i]) if (d[mini] + dist[mini][i] < d[i]) d[i] = d[mini] + dist[mini][i]; } } int main(int argc, char *argv[]) { int i, j; int u, v, w; FILE *fin = fopen("dist.txt", "r"); fscanf(fin, "%d", &e); for (i = 0; i < e; ++i) for (j = 0; j < e; ++j) dist[i][j] = 0; n = -1; for (i = 0; i < e; ++i) { fscanf(fin, "%d%d%d", &u, &v, &w); dist[u][v] = w; n = MAX(u, MAX(v, n)); } fclose(fin); dijkstra(1); printD(); return 0; } [/sourcecode] And here's a sample input file(<a href='https://compprog.files.wordpress.com/2007/12/dist.txt' title='dist.txt'>dist.txt</a>): <code>10 1 2 10 1 4 5 2 3 1 2 4 3 3 5 6 4 2 2 4 3 9 4 5 2 5 1 7 5 3 4 </code> The graph is given as an edge list: <ul> <li>the first line contains <em>e</em>, the number of edges</li> <li>the following <em>e</em> lines contain <em>3</em> numbers: <em>u</em>, <em>v</em> and <em>w</em> signifying that there's an edge from <em>u</em> to <em>v</em> of weight <em>w</em></li> </ul> That's it. Good luck and have fun. Always open to comments. <h4>Finding the shortest path</h4> <strong>UPDATE</strong> In response to <strong>campOs</strong>' comment. Now we know the distance between the source node and any other node (the distance to the ith node is remembered in <strong>d[i]</strong>). But suppose we also need the path (which nodes make up the path). Look at the above code. Where is <strong>d</strong> modified? Where is the recorded distance between the source and a node modified? In two places: Firstly, <strong>d[s]</strong> is initialised to be <em>0</em>. d[s] = 0;

And then, when a new shortest path is found, **d[i]** is updated accordingly:

for (i = 1; i <= n; ++i) if (dist[mini][i]) if (d[mini] + dist[mini][i] < d[i]) d[i] = d[mini] + dist[mini][i]; [/sourcecode] The important thing to notice here is that <strong>when you update the shortest distance to node i, you know the previous node in the path to i</strong>. This is, of course, <strong>mini</strong>. This suggests the solution to our problem. For every node <strong>i</strong> other than the source, remember not only the distance to it, but also the previous node in the path to it. Thus we have a new array, <strong>prev</strong>. Now, we need to make to modifications. First, we initialise the value of <strong>prev[i]</strong> to something impossible (say <em>-1</em>) at the start of <strong>dijkstra()</strong>. for (i = 1; i <= n; ++i) { d[i] = INFINITY; prev[i] = -1; /* no path has yet been found to i */ visited[i] = 0; /* the i-th element has not yet been visited */ } [/sourcecode] Secondly, we update the value of <strong>prev[i]</strong> every time a new shortest path is found to i. for (i = 1; i <= n; ++i) if (dist[mini][i]) if (d[mini] + dist[mini][i] < d[i]) { d[i] = d[mini] + dist[mini][i]; prev[i] = mini; } [/sourcecode] Good. For every node reachable from the source we know which node is just before it in the shortest path. For the above example, we would have the following array: <code>i - prev[i] 1 - -1 2 - 4 3 - 2 4 - 1 5 - 4 </code> Using this, how do you get the path? Let's say you want to get to <em>3</em>. Which node comes right before <em>3</em>? Node <em>2</em>. Which node comes right before node <em>2</em>? Node <em>4</em>. Which node comes before <em>4</em>? Node <em>1</em>. We've reached the source, so we're done. Go through this list backwards and you get the path: <em>1 -> 4 -> 2 -> 3</em>. This is easily implemented with <a href="http://en.wikipedia.org/wiki/Recursion">recursion</a>. void printPath(int dest) { if (prev[dest] != -1) printPath(prev[dest]); printf("%d ", dest); }

Here is the updated source: dijkstraWithPath.c.

Good luck.

2008-01-07 at 19:43

Hi, i have a direct question: how to include also the actual node path (from the specified source) along with the weight to the specific node?

tnx :)

2010-10-29 at 7:56

hat mar kela maksudi

2012-04-22 at 11:37

hello :)

I’d like to make a web service that allows to find the shortest path between bus stations with Dijkstra’s algorithm, then the path will be displayed on a map. (I have a database that contains the coordinated stations) but I do not know “how to start”: , I am really blocked for a week and i dont find any thing :( , i dont find a tutorials as this subject :( :( :(

( This web service will be used by my android application)

realy i need help :(

(i use eclipse)

thank you in advance :)

2008-01-11 at 1:17

Nice work with this blog. The algorithms are well explained, with lots of examples. It’s quite useful for programmers. I wonder if you could also post a code which obtains the k-th shortest path in a weighted graph. I’m trying to work it out using Dijkstra algorithm, but to no avail so far. Keep up the good work. Cheers. :-h

2008-01-17 at 17:12

@

campOsUpdated article. The function dijkstra() now also calculates the path, which can be printed with printPath().

Good luck.

2008-02-25 at 9:41

Can some one have the graphical implementation of dijkstra algo,Its quite difficult to implement it In C.

2008-02-29 at 12:28

hi…

thank you

:)

2008-03-09 at 5:14

Hi,

Can u send me a C program to find all possible routes

2008-03-20 at 13:10

Hi:

I’m interested in the performance.

therefore i need to implement it

using priority queues, do you have

the source code in c.

Regars,

Nathan

2008-04-27 at 12:34

Hello,

Logic and the code is very useful and easy to understand. I is helping me to greater extend. I have more than 100 nodes and I have start node and destination node, how do I specify the start node and destination node, how do I extract these are all the possible nodes for this process. Can you help me out.

Thanks

Bala

2008-08-05 at 9:52

@Bala

The start node is

s, the first parameter to void dijkstra(int s).In Dijkstra’s algorithm, there is no destination node, per se. The algorithm generates the shortest path to

allnodes.If you want the path from the source to a destination, use void printPath(int dest), where dest is the destination node.

2008-11-01 at 19:57

thx a lot.. You explain it very well

2008-11-10 at 17:46

hii……..nice work…..u help me through this in my sessionals…………

thnks alot……

2009-01-12 at 20:18

hi all….

How can i randomly generate cost matrices of size 10×10, 100×100, 1000×1000, and 10000×10000 and display

the run times ,to make input.txt file for input

if you give me some examples about it, will be great for me….

thanks……

2009-03-21 at 6:47

Hi the above code was really helpful.

I need a help from you can u send me the code for the following procedures

(1) compute the shortest paths from a given node to all other nodes

(2) print routing table at a given node, and

(3) print the shortest path between given src and dest in C.

i need to understand more in detail as my reasearch paper is mostly based on this.

thanks

2009-06-04 at 20:06

Hi!

I have one question. Is there any simply way to frezee out shortest path? Because i must find backup way for it and they must be completly diffrend. thanks

2009-06-11 at 16:24

Great work! Never before have I read such crystal clear descriptions of algorithms..not even from the classics like Sedgewick or Cormen!

2009-06-25 at 20:18

Hey thanks man. I’m curious though are you sure your algorithm works every time? I implemented it and it works for MOST cases but there are some that choose the incorrect path.

2009-08-01 at 13:42

If you are looking to further optimize the code, if you are, for example, looking to only fint the way from a single source to only 1 destination, you can stop execution at the moment your destination node gets marked as visited :)

to be precise, after this line: visited[mini] = 1;

i hope that was useful :) definetly is for me :)

PS: great algorithms man.

2009-09-23 at 19:26

to find a shortest path from a source node to a destination node in a random network:-

Read n,d and t. Create an output file (say output.txt)

Create n different nodes within the grid of dimension d. Store them in output.txt

Create the adjacency or link matrix. Store them in output.txt

Read a source and destination node from the user. Find the shortest path and output to output.txt.

Repeat the last step, until the user wishes to exit (here the option must be given to the user, either to give a source-destination pair or to exit the program)

can anyone solve tis one???

2009-10-07 at 22:14

hi

is there a way to write the code without using the file statements..or without using the .txt…like asking the user to give inputs…if yes cud u explain it ?

thanks

2009-10-22 at 10:53

scvalex,

Just a huge thanks for your work here. I used your guidance to help me fast track the porting of a PHP Dijkstra implementation of mine into C. You’ve saved me and I’m sure a lot of others a lot headaches.

Cheers,

JC

2009-11-02 at 21:02

Well explained algo.

A small bug perhaps, if we call dijkstra(2); instead of dijkstra(1); then there is a problem. It gives shortest path between 1 & 2 as 12 instead of correct 10. If someone can please check that.

2009-11-03 at 5:00

simply explained,but very effective :)

thx

2009-11-22 at 1:54

As a follow up with what A V said,

The call to dijkstra(s) with a value other then 1 will bring up the wrong value.

Does this not find the shortest path for a start node other then 1?

2009-12-01 at 11:20

A V and drico:

the call dijkstra(s) finds the shortest path from node s to all other nodes. So dijkstra(2) finds the shortest path from 2->1, 2->2, 2->3, 2->4 and 2->5. The shortest path from 2->1 is (2->4->5->1) = 12

2009-12-14 at 0:33

It would be nice if you would label your pictures.

When you say: “It’s worthwhile to note that at this step, we’ve also found a better path to node 2”, it would be nice if you provided details of how that happened. A lot of people seem to understand it, but I do not think it is clear. It just happens, without explanation. I’m looking for a detailed explanation.

2009-12-17 at 23:15

thanks a lot man! your code works very well and is very easy to understand. great job!!

2010-01-19 at 2:48

thaaaaaaaaaaaaaaaaanks

great work!!!!!!!!!!

2010-02-05 at 11:20

hi-very nice

2010-02-14 at 0:42

Hello,

Thanks a lot for the code. It semms really efficient but I need help for two cases:

1) I want to have an output that gives shortest path distances between all nodes. In otherwords, instead of writing dijkstra(1),dijkstra(2),dijkstra(3)etc. one by one, Is there anyway to get this output?

2) I want to write the output to a file. I tried “fprintf” but I could not achieve to write the output to a file.

Could you please explain these to issues in detail. Thank you for your helps.

2010-03-25 at 19:13

really gud work..its very clear and useful…thanq..

2010-04-11 at 10:58

thanx a lot …this is the best explanation of the dijkstra’s algorithm that we have come across and the best code ever…:)

2010-04-25 at 22:02

[…] here for a good reference on Djikstra’s algorithm, using an array-based […]

2010-05-10 at 2:48

thank you alots

but ,I need help you for find code for calculating the shortest path for every pair of nodes ,

such that :

input:

The number of routers in the network

and The LSPs for each router

The outputs are

The routing table for each router

2010-08-06 at 15:07

sir i need shortest path algorithm in c with graphical output and atleast of three authors implementation.s sir i need three authors implementation of same process with individuals.

2010-09-12 at 11:59

it is very nice to understand .

helm me more to know how this worrk.

nice jobe

2010-12-27 at 9:33

could pls send me the c code to print route table.

2011-05-07 at 19:21

You state that the shortest path from 1->3 is 1 -> 4 -> 2 -> 3 of length 9.

Wouldn’t this be length 8 and not 9?

2011-05-11 at 10:12

Q1: #define GRAPHSIZE xxxx is this must be larger than the # of edges?

Q2: I have tried to run your code on a large graph (100 node & 9900 edges including some edges that have 0-weight) but it didn’t work?! Specially edges with large weights.

2011-07-05 at 15:21

[…] The following programme just puts the bellman_ford function into context. It runs in O(VE) time, so for the example graph it will do something on the lines of 5 * 9 = 45 relaxations. Keep in mind that this algorithm works quite well on graphs with few edges, but is very slow for dense graphs (graphs with almost n2 edges). For graphs with lots of edges, you’re better off with Dijkstra’s algorithm. […]

2011-08-22 at 9:02

Hi,

thanks for the algorithm; it works fine with a small graph, but I tried with 30000 nodes and 163570 edges and I receive a “bus error”.

I’m using a macbook with 8GB ram and I put GRAPHSIZE= 30000.

Is there something I can do?

Thanks

E.

2011-08-23 at 1:52

Ok, the problem was that GRAPHSIZE should be set as 163570, right? But with this big number I receive an error because INFINITY become bigger than the max integer number, so I just put a big number instead of d[i] = INFINITY and now it seems to work but it is very slow.

2011-08-23 at 2:32

Actually there is something that I still don’t understand:

The graphsize constant should be the number of edges… So why we have to declare it if we take it in input from the distances file?

If graphsize is the number of edges why we use it to define the dist matrix, that should be NxN where N is the number of nodes?

Thanks

2011-09-05 at 12:14

This code doesn’t work if you have a node called 0 and want to calculate the paths from 0 to all other nodes.

2011-09-09 at 9:55

Hi,

How come i cannot access the file dist.txt?

2011-09-12 at 1:12

good job

2011-09-12 at 12:55

Hi,

Information provided was very helpful.

How can we print all possible paths from source to destination?

Can you please help regarding this?

2011-09-13 at 13:21

Can any one explain this code/algoritm. The code is in python and ‘m not familiar with python

Say I have nodes connected in the below fashion, how do I arrive at the number of paths that exist between given points, and path details?

1,2 //node 1 and 2 are connected

2,3

2,5

4,2

5,11

11,12

6,7

5,6

3,6

6,8

8,10

8,9

Find the paths from 1 to 7:

Answer: 2 paths found and they are

1,2,3,6,7

1,2,5,6,7

# a sample graph

graph = {‘A’: [‘B’, ‘C’,’E’],

‘B’: [‘A’,’C’, ‘D’],

‘C’: [‘D’],

‘D’: [‘C’],

‘E’: [‘F’,’D’],

‘F’: [‘C’]}

class MyQUEUE: # just an implementation of a queue

def __init__(self):

self.holder = []

def enqueue(self,val):

self.holder.append(val)

def dequeue(self):

val = None

try:

val = self.holder[0]

if len(self.holder) == 1:

self.holder = []

else:

self.holder = self.holder[1:]

except:

pass

return val

def IsEmpty(self):

result = False

if len(self.holder) == 0:

result = True

return result

path_queue = MyQUEUE() # now we make a queue

def BFS(graph,start,end,q):

temp_path = [start]

q.enqueue(temp_path)

while q.IsEmpty() == False:

tmp_path = q.dequeue()

last_node = tmp_path[len(tmp_path)-1]

print tmp_path

if last_node == end:

print “VALID_PATH : “,tmp_path

for link_node in graph[last_node]:

if link_node not in tmp_path:

#new_path = []

new_path = tmp_path + [link_node]

q.enqueue(new_path)

BFS(graph,”A”,”D”,path_queue)

————-results——————-

[‘A’]

[‘A’, ‘B’]

[‘A’, ‘C’]

[‘A’, ‘E’]

[‘A’, ‘B’, ‘C’]

[‘A’, ‘B’, ‘D’]

VALID_PATH : [‘A’, ‘B’, ‘D’]

[‘A’, ‘C’, ‘D’]

VALID_PATH : [‘A’, ‘C’, ‘D’]

[‘A’, ‘E’, ‘F’]

[‘A’, ‘E’, ‘D’]

VALID_PATH : [‘A’, ‘E’, ‘D’]

[‘A’, ‘B’, ‘C’, ‘D’]

VALID_PATH : [‘A’, ‘B’, ‘C’, ‘D’]

[‘A’, ‘E’, ‘F’, ‘C’]

[‘A’, ‘E’, ‘F’, ‘C’, ‘D’]

VALID_PATH : [‘A’, ‘E’, ‘F’, ‘C’, ‘D’]

2011-09-23 at 12:51

#include

static struct

{

int value1;

int value2;

int used;

}

data[] = {

{ 1, 2 },

{ 1, 4 },

{ 2, 3 },

{ 2, 4 },

{ 4, 5 },

{ 1, 5 },

{ 5, 3 },

};

enum { DATA_SIZE = sizeof data / sizeof *data };

static int output[DATA_SIZE];

int traverse( int from, int to, int depth )

{

int i;

output[depth++] = from;

if (from == to)

{

for (i = 0; i “);

}

printf(“%d”, output[i]);

}

printf(“\n”);

}

else

{

for (i = 0; i < DATA_SIZE; i++)

{

if (!data[i].used)

{

data[i].used = 1;

if (from == data[i].value1)

{

traverse(data[i].value2, to, depth);

}

else if (from == data[i].value2)

{

traverse(data[i].value1, to, depth);

}

data[i].used = 0;

}

}

}

return 0;

}

int main()

{

printf("The paths are\n\n\n");

traverse(1, 5, 0);

return 0;

}

2011-09-28 at 10:35

Thatnks a lot everything is sxplained nicely. But I have a Question.

What does the ((a > b) ? (a) : (b)) in line

#define MAX(a, b) ((a > b) ? (a) : (b)) mean? What does it? Thanks in advance and keep up the good work

2013-01-10 at 4:43

#define MAX(a,b) ((a>b) ? (a) : (b))

means

return is int

int MAX( int a, int b)

{

int nReturn;

if( a > b ) // a > b

{

nReturn = a;

}

else // a

return value not fixed.um….. my english is bad, u can understand it ?2011-10-07 at 13:00

What i need to change to make this code work in undirected graph?

2011-11-02 at 16:10

thanx a lot for share,,it’s helpfull for me..

may i modified this source?

keep up a good work..

2011-11-04 at 22:36

Battlefield 3 forums…[…]One Source Shortest Path: Dijkstra’s Algorithm « Computer programming[…]…

2011-11-09 at 15:27

one-way-links…[…]One Source Shortest Path: Dijkstra’s Algorithm « Computer programming[…]…

2011-11-10 at 3:13

Vlasic…[…]One Source Shortest Path: Dijkstra’s Algorithm « Computer programming[…]…

2011-11-21 at 17:18

plz send the source code of the program in which you have created file “dist.txt”

2011-11-21 at 18:20

hey…i’ve created the file “dist.txt”

But there is one error coming…when i traced it..i found dat when the loop is executed 2nd time…it terminates at n=MAX(u, MAX(v, n)) in

for (i = 0; i < e; ++i)

{

fscanf(fin, "%d%d%d", &u, &v, &w);

dist[u][v] = w;

n = MAX(u, MAX(v, n));

}

I dont knw why…i used the same input dat u wrote in dist.txt

Help…!!!

2011-12-21 at 13:49

Link Shortener…[…]One Source Shortest Path: Dijkstra’s Algorithm « Computer programming[…]…

2011-12-25 at 23:40

Battlefield 3 Cheats…[…]One Source Shortest Path: Dijkstra’s Algorithm « Computer programming[…]…

2012-01-04 at 12:01

SmokeStik Coupon…[…]One Source Shortest Path: Dijkstra’s Algorithm « Computer programming[…]…

2012-01-24 at 7:19

[cluster headache|headache relief|headache sufferers|migraine cures|migraine headaches|migraine symptoms|natural headache remedies|naturopathic approach|pharmacy times]…[…]One Source Shortest Path: Dijkstra’s Algorithm « Computer programming[…]…

2012-03-14 at 16:07

hi… i got this infile with data .

5

0 1 5 0 0

1 0 0 2 4

5 0 0 2 3

0 2 2 0 1

0 4 3 1 0

and the following code for dijkstra which i ve got problem. Its a mix of my ideas and your code above.

Could you help me?

I have stucked for about a week and i cant find what i should do.

#include

#include

#include

#define MAX_NODES 5

struct node{

int distance;

int label; // 0 –> unsolved , 1 –>solved

int path;

int previous;

struct node *next;

}Node[MAX_NODES],*head,*dummy;

void add_node_to_list(int x){

dummy=(struct node*)calloc(1,sizeof(Node));

dummy->path=x;

//dummy->previous=y;

dummy->next=head;

head=dummy;

}

void display_all_nodes(){

dummy=head;

while(dummy != NULL){

printf(“%d\t”,dummy->path);

// printf(“%d\t”,dummy->previous);

dummy=dummy->next;

}

}

main(){

//===DECLARATIONS START============================================================

double start = clock() ;

double end , cpu_time_used;

int i, j, n, min,next,global_min=0,prior,k;

int **dis;

FILE*fp=fopen(“data.txt”,”r”);

head=NULL;

dummy=(struct node*)calloc(1,sizeof(Node));

fscanf(fp,”%d”,&n);

printf(“\n%d\n”,n);

dis=(int**)calloc(n,sizeof(int));

for(i=0;i<n;i++){

dis[i]=(int*)calloc(n,sizeof(int));

}

//====DECLARATIONS END=============================================================

//===READ DATA FROM FILE START=====================================================

for(i=0;i<n;i++){

for(j=0;j<n;j++){

fscanf(fp,"%d",&dis[i][j]);

printf("%d\t",dis[i][j]);

}

printf("\n");

}

printf("\n\n");

fclose(fp);

//====READ DATA FROM FILE END=======================================================

//====INITIALIZATION START=======================================================

for(i=0;i<n;i++){

Node[i].label=0;

Node[i].distance=999;

Node[i].previous=0;

}

Node[0].label=1; //I declare node 0 as solved.

Node[0].distance=0;

add_node_to_list(0); //make node 0 as solved because from there i ll start

//====INITIALIZATION END=======================================================

while(Node[n-1].label==0){

for(k=0;k<n;k++){

min=-1;

for(i=0;i<n;i++)

if((Node[i].label==0) && ((min == -1) || (Node[i].distance < Node[min].distance)))

min=i;

Node[min].label=1;

//add_node_to_list(min);

for(j=0;j 0)

if(Node[min].distance + dis[min][j] next);

free(head);

end=clock();

cpu_time_used=((double)(end-start)/CLOCKS_PER_SEC);

printf(“\ncpu_time_used:%.6lf sec\n”,cpu_time_used);

system(“pause”);

}

2012-03-18 at 8:59

You can send help me file dijktra_mpi.c

2012-03-22 at 22:49

How would you change the original code to read strings? An example input test file would be:

5

chi stl 200

chi ny 1000

stl springfield 50

springfield chi 75

springfield ny 1100

2012-11-24 at 23:09

thank you so much.

ขอบคุณมากครับ

2012-11-30 at 9:32

you have 1 small mistake

short path betwen node 3 and node 4 = 3 , not 9

thank`s

2012-12-04 at 11:14

Thank you so very much, scvalex…

your code is amazing and helps me a lot :)

2012-12-31 at 18:08

[…] https://compprog.wordpress.com/2007/12/01/one-source-shortest-path-dijkstras-algorithm/ […]

2013-02-05 at 14:26

Dear scvalex,

Thank you so much for your effort. After running your code I found a problem. When the edge between two nodes has cost equal zero the algorithm is not taking into account the edge when it’s searching the shortest path. Do you have any suggestion for fixing it?

Thank you,

Regards

2013-03-27 at 20:54

Can`t download dist.txt, help please…

2014-04-24 at 8:39

why I cn’t dwload the dist.txt file? please help..tq

2014-10-16 at 12:28

It’s an remarkable piece of writing in favor of all the web visitors; they will take advantage

from it I am sure.

2015-03-11 at 19:04

can u write this code in verilog

2015-03-26 at 18:34

Can i get a code in java…….? I need it real bad!!!!!!!!!!!!!!!!!

2015-06-08 at 0:24

What if i want use weight matrix 5×5 not 10×3, how do i change the code?

2015-09-07 at 4:06

newbie here. what if i use character names instead of integer values. how will the program change?

2015-12-06 at 14:53

did you solve it? same problem.