Dijkstra’s Algorithm in C

Created: December 30, 2012,  
The Author: Mufaddal Makati
Last Updated: July 7, 2014

Dijkstra’s algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms.

— Wikipedia

Download Package

Download Package

Here is an implementation of dijkstra’s algorithm in C programming language. I have tried to document it a little.

It should work on all linux platforms. The graph.ospf file serves as an input file which contains the graph that the program will use. Make sure to put both – the source file and the graph.ospf file in the same directory. 

Either Copy the code and input file below or download the package.

 C |  copy code |? 
001
/* 
002
 * Author: Mufaddal Makati
003
   Official Post: http://www.rawbytes.com
004
 Copyright [2010] [Author: Mufaddal Makati]
005
 
006
   Licensed under the Apache License, Version 2.0 (the "License");
007
   you may not use this file except in compliance with the License.
008
   You may obtain a copy of the License at
009
 
010
       http://www.apache.org/licenses/LICENSE-2.0
011
 
012
   Unless required by applicable law or agreed to in writing, software
013
   distributed under the License is distributed on an "AS IS" BASIS,
014
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015
   See the License for the specific language governing permissions and
016
   limitations under the License.
017
 *
018
 * Created on September, 2010.
019
 */
020
#include <stdio.h>
021
#include <stdlib.h>
022
#include <string.h>
023
#define MAX_CONN 10
024
#define MAX_NODES 50
025
#define INFINITE 9999
026
/*
027
 *
028
 */
029
void view(); /* just prints out the graph*/
030
void djkstra(); /*runs at the begining and when file is rescaned*/
031
void min_route();
032
void scanfile(); /*it does not check for wrong format of the file.it is up to the user to verify it.*/
033
struct node /*data structure to store information of each node*/
034
{
035
    int id; 
036
    struct node *l[MAX_CONN+1]; /*array that points to all other nodes connected with this node*/
037
    int cost[MAX_CONN+1];  /*array that stores cost of all connections with this node*/
038
    struct node **next; /*address of the pointer of the next node to traverse, for the ith destination node in the array of records datastructure*/
039
    int *mincost;/*minimum cost to traverse the ith destination node in the array of records datastructure*/
040
};
041
typedef struct node nodes; 
042
struct record /* data structure to map node id and corresponding address of nodes structure.*/
043
{
044
    int nid;
045
    struct node *add;
046
};
047
typedef struct record records;
048
records nlist[MAX_NODES+1]={0}; /*create array of records and mark the end of the array with zero.*/
049
int count; /*stores number of nodes*/
050
 
051
int main()
052
{
053
    int c;
054
    nlist[MAX_NODES+1].nid=0;
055
    system("clear");
056
 
057
    scanfile();
058
    printf("\nSucessfully Scanned the graph.\n");
059
    djkstra();
060
 
061
    for(;;)
062
    {
063
        view();
064
 
065
        printf("\n1.Rescan file.");
066
        printf("\n2.View minimum route between nodes.");
067
        printf("\n3.Exit.");
068
        printf("\nEnter:");
069
        scanf("%d",&c);
070
        switch(c)
071
        {
072
            case 1:
073
            {
074
                scanfile();
075
                djkstra();
076
                system("clear");
077
                break;
078
            }
079
            case 2:
080
            {
081
                min_route();
082
                system("clear");
083
                break;
084
            }
085
            case 3:
086
            {
087
                exit(0);
088
            }
089
            default:
090
            {
091
                printf("\nEnter proper choice.\n");
092
                break;
093
            }
094
        }        
095
    }
096
    return (EXIT_SUCCESS);
097
}
098
 
099
void scanfile()
100
{
101
    FILE *f;
102
    int d;
103
    int i=0,j=0,n_id,n_cost;
104
    nodes *temp=0,*temp1=0;
105
 
106
    if((f=fopen("graph.ospf","r"))== NULL)
107
    {
108
        printf("Error opening file.\n");
109
        exit(1);
110
    }
111
    memset(nlist, 0, sizeof(struct record) * MAX_NODES);
112
    count=0;
113
    do /*first get the id and address of all nodes*/
114
    {
115
        fscanf(f,"%d",&n_id);
116
        for(i=0;nlist[i].nid!=0;i++)
117
        {
118
            if(n_id==nlist[i].nid)
119
            {
120
                printf("Id already exists.");
121
                return;
122
            }
123
        }
124
        temp=(nodes *)malloc(sizeof(nodes));
125
        if (temp == 0)
126
        {
127
           printf("ERROR: Out of memory\n");
128
           return;
129
        }
130
        memset(temp, 0, sizeof(struct node));
131
        temp->id=n_id;
132
        temp->l[MAX_CONN+1]=0;
133
        temp->cost[MAX_CONN+1]=0;
134
        for(i=0;nlist[i].nid!=0;i++)
135
        {}
136
        nlist[i].nid=n_id;
137
        nlist[i].add=temp;
138
        count++;
139
        while((d=fgetc(f)!=';'))
140
        {}
141
    }while((d=fgetc(f))!=EOF);
142
 
143
    rewind(f);
144
 
145
    for(i=0;i<count;i++) /*now get the information of all nodes connections.*/
146
    {
147
        fscanf(f,"%*d");
148
        temp=nlist[i].add;
149
        while((d=fgetc(f)!=';'))
150
        {
151
            fscanf(f,"%d-%d",&n_id,&n_cost);
152
            for(j=0;nlist[j].nid!=0;j++)
153
            {
154
                if(nlist[j].nid==n_id)
155
                {
156
                    temp1=nlist[j].add;
157
                    break;
158
                }
159
            }
160
            for(j=0;temp->cost[j]!=0;j++)
161
            {}
162
            temp->cost[j]=n_cost;
163
            temp->l[j]=temp1;
164
        }
165
    }
166
    fclose(f);
167
}
168
 
169
void view()
170
{
171
    int i,j;
172
    nodes *temp=0,*temp1=0;
173
 
174
    printf("\nID\tConnceted to- ID:cost");
175
    for(i=0;nlist[i].nid!=0;i++)
176
    {
177
        printf("\n%d",nlist[i].nid);
178
        temp=nlist[i].add;
179
        for(j=0;temp->l[j]!=0;j++)
180
        {
181
            temp1=temp->l[j];
182
            printf("\t%d:%d",temp1->id,temp->cost[j]);
183
        }
184
    }
185
    printf("\n \n \n");
186
}
187
 
188
void djkstra()
189
{
190
    int i,j,k,num,num1=0,min=INFINITE;
191
    int *tcost=0,*done=0;
192
    nodes *temp=0,*temp1=0,**tent=0;
193
 
194
    tcost=(int*)calloc(count, sizeof(int));
195
    if (tcost == 0)
196
    {
197
 printf("ERROR: Out of memory\n");
198
 return;
199
    }
200
    done=(int*)calloc(count, sizeof(int));
201
    if (done == 0)
202
    {
203
 printf("ERROR: Out of memory\n");
204
 return;
205
    }
206
    tent=(nodes**)calloc(count, sizeof(nodes));
207
    if (tent == 0)
208
    {
209
 printf("ERROR: Out of memory\n");
210
 return;
211
    }
212
 
213
    for(i=0;nlist[i].nid!=0;i++)
214
    {
215
         for(j=0;j<count;j++)
216
         {
217
            tcost[j]=INFINITE;
218
            done[j]=0;
219
         }
220
        temp=nlist[i].add;
221
        temp->next=(nodes**)calloc(count, sizeof(nodes));
222
        temp->mincost=(int*)calloc(count, sizeof(int));
223
        tcost[i]=0;
224
        done[i]=1;
225
        temp->mincost[i]=0;
226
        temp1=temp;
227
        for(;;)
228
        {
229
            for(num1=0;nlist[num1].nid!=0;num1++)
230
            {
231
                if(nlist[num1].add==temp1)
232
                    break;
233
            }
234
            for(k=0;temp1->l[k]!=0;k++)
235
            {
236
                for(num=0;nlist[num].nid!=0;num++)
237
                {
238
                    if(nlist[num].add==temp1->l[k])
239
                        break;
240
                }
241
 
242
                if(tcost[num] > (tcost[num1]+temp1->cost[k]))
243
                {
244
                    tcost[num]= tcost[num1] + temp1->cost[k];
245
                    if(temp1==temp)
246
                        tent[num]=temp1->l[k];
247
                    else
248
                        tent[num]=tent[num1];
249
                }
250
            }
251
            min=INFINITE;num1=0;
252
            for(j=0;j<count;j++)
253
            {
254
                if(tcost[j]<min && done[j]!=1 && tcost[j]!=0)
255
                {
256
                    min=tcost[j];
257
                    num1=j;
258
                }
259
            }
260
            if(min==INFINITE)
261
                break;
262
 
263
            temp1=nlist[num1].add;
264
            temp->mincost[num1]=tcost[num1];
265
            temp->next[num1]=tent[num1];
266
            done[num1]=1;
267
        }
268
    }
269
}
270
 
271
void min_route()
272
{
273
    int i,sid,did,num,chk=0;
274
    nodes *temp=0,*temp1=0;
275
 
276
        printf("\nEnter source node ID:");
277
        scanf("%d",&sid);
278
        printf("\nEnter destination node ID:");
279
        scanf("%d",&did);
280
 
281
        for(i=0;nlist[i].nid!=0;i++)
282
        {
283
            temp=nlist[i].add;
284
            if(temp->id==sid)
285
            {
286
                chk=1;
287
                break;
288
            }
289
        }
290
        if(chk==0)
291
        {
292
            printf("\nSource Id not found.\n");
293
            return;
294
        }
295
        chk=0;
296
        for(num=0;nlist[num].nid!=0;num++)
297
        {
298
            temp1=nlist[num].add;
299
            if(temp1->id==did)
300
            {
301
                chk=1;
302
                break;
303
            }
304
        }
305
        if(chk==0)
306
        {
307
            printf("\nDestination Id not found.\n");
308
            return;
309
        }
310
        printf("%d-",temp->id);
311
        temp1=temp;
312
        for(;;)
313
        {
314
            if(temp1->id==did)
315
                break;
316
            if(temp1->next[num]!=0)
317
            {
318
                temp1=temp1->next[num];
319
                printf("-%d-",temp1->id);
320
            }
321
            else
322
            {
323
                printf("No Route");
324
                break;
325
            }
326
        }
327
        printf("\nTotal cost:%d",temp->mincost[num]);
328
}
329

How to write a graph in graph.ospf file: -

  • Each line stands for a single node. The format of each line is - node id:id of node it is connected to-corresponding cost:id of node it is connected to-corresponding cost:…;
  • Each line terminates with a ‘;’
  • Please note that there is no extra space or newline after the last ; of the last line.

The Graph shown here in the sample graph.ospf corresponds to this graph -

dijkstra's graph

dijkstra’s graph

Here’s a sample graph.ospf file: -

 Text |  copy code |? 
1
1:2-2:3-4:5-4;
2
2:1-2:3-3;
3
3:1-4:2-3:5-6:6-7;
4
4:6-8;
5
5:1-4:3-6;
6
6:3-7:4-8;

I have not written any defensive code to check for the correct format of the input file. So if you are experiencing any strange behavior from the program, please check the format of your input file.

This program is not heavily tested.

Comments

comments