## Bellman ford algorithm in C

Let's talk about algorithms!

Moderator: Board moderators

laboni
New poster
Posts: 12
Joined: Sat Sep 14, 2002 9:22 pm
Location: India

### Bellman ford algorithm in C

hi!
I read the Bellman-ford algorithm but just can't code it.
I need the code very very much.
I know it is not good to ask for source codes here, and in fact
i should not ask for it , but i have little time in hand i need
a source code for BELLMAN-FORD algorithm to find the
shortest path in a graph in C.

So somebody help me by sending source-code of the algorithm in C.
Bye.

laboni
New poster
Posts: 12
Joined: Sat Sep 14, 2002 9:22 pm
Location: India

### Is there any one - Hello?

If anyone have problem sending bellman ford in this board but wants to send me personally - requested to mail me <laboni_inobal@yahoo.com>

bye
Laboni

suman
New poster
Posts: 45
Joined: Fri Oct 19, 2001 2:00 am
Contact:

### An Implementation

Hi,
Here is an implementation done by Sadi Khan, Sadi_Khan_mail@yahoo.com , one of my friend. I believe he wont mind posting the code here. I may delete this post if he does. I am not sure about the correctness of this program. More over don't know about the complexity. It was done more or less using the approach described in the book of CLRS. Hope this will help you. One request as the code is not mine, use it with the author name inside the code (please). If you want a C++ implementation of the algorithm, I will be happy to give you the one of mine. My email (udvranto@hotmail.com).

Best of luck.

Program
[cpp]
/*
Created by Sadi Khan
mail: Sadi_Khan_mail@yahoo.com
*/
#include <string.h>
#include <stdio.h>

#ifndef ONLINE_JUDGE
#define IN
#define IN_FILE "spath.txt"
// #include <online.h>
#endif

#define INF 16000

typedef struct
{
int Destination;
int Weight;
} PATH;

typedef struct
{ bool Mark; /* useful during calculation, true = visited */
char Name;
int TotalPath;
PATH Paths[26];
} NODE;

NODE Nodes[26]; /* Nodes can be assigned as A - Z */

int Shortest[26];
int Source[26];

/**********************************************/
/* */
/**********************************************/
void ReadPath()
{
int Path;
int From,To;
char t1[2],t2[2];
int c,mg;

memset(Nodes,0,sizeof(Nodes));

scanf("%d",&Path);

while(Path-->0)
{
scanf("%s %s %d",t1,t2,&mg);
From = t1[0];
To = t2[0];
c = Nodes[From-'A'].TotalPath++;
Nodes[From-'A'].Paths[c].Destination=To-'A';
Nodes[From-'A'].Paths[c].Weight=mg;

c = Nodes[To-'A'].TotalPath++;
Nodes[To-'A'].Paths[c].Destination=From-'A';
Nodes[To-'A'].Paths[c].Weight=mg;
}
}
/**********************************************/
/* Bellman-Ford algorithm */
/**********************************************/
void Init(int start)
{
int n;
for(n=0; n<26; n++)
{ Shortest[n] = INF;
Source[n] = -1;
}
Shortest[start] = 0;
}

inline bool Relax(int u,int v,int w)
{
if(Shortest[ u ] > Shortest[v] + w)
{ Shortest [ u ] = Shortest[v] + w;
Source [ u ] = v;
return true;
}

if(Shortest [ u ] == Shortest[v] + w && Source[ u ] < v)
{ Shortest [ u ] = Shortest[v] + w;
Source [ u ] = v;
return true;
}

return false;
}

void BellmanFord(int start)
{
int i,n,f;

Init(start);

do{
f = false;
for(i=0;i<26;i++)
for(n=0;n<Nodes.TotalPath;n++)
f |= Relax(i,Nodes.Paths[n].Destination,
Nodes.Paths[n].Weight);
} while(f);

}

/**********************************************/
/* */
/**********************************************/
int main()
{
int a,b,p,n;
char t1[2],t2[2];
ReadPath();

while(scanf("%s %s",t1,t2)==2)
{ a=t1[0];b=t2[0];

BellmanFord(a-'A');
p = Shortest[b-'A'];

if(p < INF)
{ printf("The shortest path from %c to %c is %d\n",a,b,p);
a-='A';b-='A';

int Temp[26];
int n=0;

Temp[n++] = b;
do
{
Temp[n++] = Source;
b = Source;

} while(a!=b);

while(n-- > 0)
printf("%c ",Temp[n]+'A');

printf("\n\n");

}
}
return 0;
}

[/cpp]

Input

Code: Select all

``````325
A B 47
A C 31
A D 83
A E 91
A F 57
A G 18
A H 96
A I 16
A J 49
A K 27
A L 5
A M 59
A N 72
A O 80
A P 93
A Q 61
A R 13
A S 22
A T 64
A U 48
A V 20
A W 42
A X 91
A Y 86
A Z 15
B C 10
B D 53
B E 72
B F 80
B G 17
B H 82
B I 52
B J 96
B K 94
B L 35
B M 11
B N 80
B O 96
B P 62
B Q 93
B R 90
B S 89
B T 67
B U 65
B V 93
B W 64
B X 67
B Y 65
B Z 40
C D 52
C E 28
C F 1
C G 96
C H 13
C I 9
C J 67
C K 48
C L 43
C M 75
C N 70
C O 90
C P 84
C Q 67
C R 42
C S 91
C T 79
C U 66
C V 80
C W 91
C X 34
C Y 54
C Z 30
D E 86
D F 23
D G 34
D H 38
D I 37
D J 69
D K 61
D L 59
D M 37
D N 61
D O 43
D P 43
D Q 68
D R 16
D S 17
D T 19
D U 57
D V 80
D W 9
D X 60
D Y 62
D Z 98
E F 56
E G 82
E H 76
E I 41
E J 91
E K 2
E L 38
E M 36
E N 44
E O 68
E P 13
E Q 12
E R 34
E S 94
E T 55
E U 54
E V 27
E W 19
E X 87
E Y 71
E Z 85
F G 15
F H 32
F I 100
F J 87
F K 31
F L 5
F M 92
F N 93
F O 16
F P 44
F Q 47
F R 85
F S 81
F T 69
F U 5
F V 80
F W 29
F X 66
F Y 67
F Z 36
G H 41
G I 24
G J 81
G K 79
G L 37
G M 28
G N 65
G O 49
G P 21
G Q 14
G R 46
G S 50
G T 44
G U 81
G V 73
G W 26
G X 92
G Y 100
G Z 23
H I 45
H J 32
H K 81
H L 71
H M 22
H N 77
H O 4
H P 6
H Q 23
H R 93
H S 14
H T 79
H U 73
H V 22
H W 82
H X 62
H Y 33
H Z 83
I J 63
I K 75
I L 19
I M 6
I N 90
I O 24
I P 53
I Q 37
I R 66
I S 66
I T 80
I U 84
I V 63
I W 27
I X 10
I Y 14
I Z 80
J K 68
J L 11
J M 47
J N 24
J O 53
J P 29
J Q 78
J R 14
J S 47
J T 36
J U 48
J V 95
J W 26
J X 79
J Y 64
J Z 64
K L 75
K M 60
K N 12
K O 32
K P 82
K Q 100
K R 52
K S 4
K T 99
K U 95
K V 65
K W 57
K X 94
K Y 48
K Z 88
L M 73
L N 33
L O 27
L P 63
L Q 86
L R 94
L S 26
L T 49
L U 31
L V 8
L W 5
L X 17
L Y 19
L Z 85
M N 27
M O 97
M P 95
M Q 22
M R 70
M S 44
M T 67
M U 43
M V 41
M W 96
M X 1
M Y 89
M Z 56
N O 13
N P 58
N Q 92
N R 7
N S 25
N T 89
N U 12
N V 19
N W 62
N X 52
N Y 84
N Z 97
O P 52
O Q 83
O R 50
O S 36
O T 99
O U 51
O V 96
O W 63
O X 76
O Y 17
O Z 23
P Q 47
P R 75
P S 36
P T 60
P U 57
P V 57
P W 64
P X 4
P Y 50
P Z 50
Q R 23
Q S 30
Q T 22
Q U 81
Q V 86
Q W 10
Q X 71
Q Y 82
Q Z 72
R S 87
R T 44
R U 52
R V 61
R W 24
R X 81
R Y 25
R Z 71
S T 19
S U 68
S V 82
S W 17
S X 47
S Y 60
S Z 7
T U 86
T V 40
T W 72
T X 6
T Y 22
T Z 3
U V 67
U W 55
U X 14
U Y 19
U Z 46
V W 60
V X 15
V Y 22
V Z 3
W X 93
W Y 66
W Z 9
X Y 21
X Z 94
Y Z 38

A Z
Z A
B X
X B
R T
T R
A B
B A
A C
C A
F P
P F
Q R
R Q
S Z
Z S
Y Z
Z Y

A B
B A
A C
C A
A D
D A
A E
E A
A F
F A
A G
G A
A H
H A
A I
I A
A J
J A
A K
K A
A L
L A
A M
M A
A N
N A
A O
O A
A P
P A
A Q
Q A
A R
R A
A S
S A
A T
T A
A U
U A
A V
V A
A W
W A
A X
X A
A Y
Y A
A Z
Z A
B C
C B
B D
D B
B E
E B
B F
F B
B G
G B
B H
H B
B I
I B
B J
J B
B K
K B
B L
L B
B M
M B
B N
N B
B O
O B
B P
P B
B Q
Q B
B R
R B
B S
S B
B T
T B
B U
U B
B V
V B
B W
W B
B X
X B
B Y
Y B
B Z
Z B
C D
D C
C E
E C
C F
F C
C G
G C
C H
H C
C I
I C
C J
J C
C K
K C
C L
L C
C M
M C
C N
N C
C O
O C
C P
P C
C Q
Q C
C R
R C
C S
S C
C T
T C
C U
U C
C V
V C
C W
W C
C X
X C
C Y
Y C
C Z
Z C
D E
E D
D F
F D
D G
G D
D H
H D
D I
I D
D J
J D
D K
K D
D L
L D
D M
M D
D N
N D
D O
O D
D P
P D
D Q
Q D
D R
R D
D S
S D
D T
T D
D U
U D
D V
V D
D W
W D
D X
X D
D Y
Y D
D Z
Z D
E F
F E
E G
G E
E H
H E
E I
I E
E J
J E
E K
K E
E L
L E
E M
M E
E N
N E
E O
O E
E P
P E
E Q
Q E
E R
R E
E S
S E
E T
T E
E U
U E
E V
V E
E W
W E
E X
X E
E Y
Y E
E Z
Z E
F G
G F
F H
H F
F I
I F
F J
J F
F K
K F
F L
L F
F M
M F
F N
N F
F O
O F
F P
P F
F Q
Q F
F R
R F
F S
S F
F T
T F
F U
U F
F V
V F
F W
W F
F X
X F
F Y
Y F
F Z
Z F
G H
H G
G I
I G
G J
J G
G K
K G
G L
L G
G M
M G
G N
N G
G O
O G
G P
P G
G Q
Q G
G R
R G
G S
S G
G T
T G
G U
U G
G V
V G
G W
W G
G X
X G
G Y
Y G
G Z
Z G
H I
I H
H J
J H
H K
K H
H L
L H
H M
M H
H N
N H
H O
O H
H P
P H
H Q
Q H
H R
R H
H S
S H
H T
T H
H U
U H
H V
V H
H W
W H
H X
X H
H Y
Y H
H Z
Z H
I J
J I
I K
K I
I L
L I
I M
M I
I N
N I
I O
O I
I P
P I
I Q
Q I
I R
R I
I S
S I
I T
T I
I U
U I
I V
V I
I W
W I
I X
X I
I Y
Y I
I Z
Z I
J K
K J
J L
L J
J M
M J
J N
N J
J O
O J
J P
P J
J Q
Q J
J R
R J
J S
S J
J T
T J
J U
U J
J V
V J
J W
W J
J X
X J
J Y
Y J
J Z
Z J
K L
L K
K M
M K
K N
N K
K O
O K
K P
P K
K Q
Q K
K R
R K
K S
S K
K T
T K
K U
U K
K V
V K
K W
W K
K X
X K
K Y
Y K
K Z
Z K
L M
M L
L N
N L
L O
O L
L P
P L
L Q
Q L
L R
R L
L S
S L
L T
T L
L U
U L
L V
V L
L W
W L
L X
X L
L Y
Y L
L Z
Z L
M N
N M
M O
O M
M P
P M
M Q
Q M
M R
R M
M S
S M
M T
T M
M U
U M
M V
V M
M W
W M
M X
X M
M Y
Y M
M Z
Z M
N O
O N
N P
P N
N Q
Q N
N R
R N
N S
S N
N T
T N
N U
U N
N V
V N
N W
W N
N X
X N
N Y
Y N
N Z
Z N
O P
P O
O Q
Q O
O R
R O
O S
S O
O T
T O
O U
U O
O V
V O
O W
W O
O X
X O
O Y
Y O
O Z
Z O
P Q
Q P
P R
R P
P S
S P
P T
T P
P U
U P
P V
V P
P W
W P
P X
X P
P Y
Y P
P Z
Z P
Q R
R Q
Q S
S Q
Q T
T Q
Q U
U Q
Q V
V Q
Q W
W Q
Q X
X Q
Q Y
Y Q
Q Z
Z Q
R S
S R
R T
T R
R U
U R
R V
V R
R W
W R
R X
X R
R Y
Y R
R Z
Z R
S T
T S
S U
U S
S V
V S
S W
W S
S X
X S
S Y
Y S
S Z
Z S
T U
U T
T V
V T
T W
W T
T X
X T
T Y
Y T
T Z
Z T
U V
V U
U W
W U
U X
X U
U Y
Y U
U Z
Z U
V W
W V
V X
X V
V Y
Y V
V Z
Z V
W X
X W
W Y
Y W
W Z
Z W
X Y
Y X
X Z
Z X
Y Z
Z Y
``````

- Suman

laboni
New poster
Posts: 12
Joined: Sat Sep 14, 2002 9:22 pm
Location: India

### Thanks a lot

Suman,

Thank u very much for the code.
I hope this would work for me.
Thanks again.

Bye

Laboni