Bellman ford algorithm in C

Let's talk about algorithms!

Moderator: Board moderators

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

Bellman ford algorithm in C

Post by laboni » Wed Nov 27, 2002 4:45 pm

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?

Post by laboni » Sat Nov 30, 2002 10:16 pm

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

Post by suman » Sun Dec 01, 2002 4:46 pm

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

Post by laboni » Tue Dec 03, 2002 8:33 pm

Suman,

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

Bye

Laboni

Post Reply

Return to “Algorithms”