Bellman–Ford algorithm: Difference between revisions

Revision as of 14:46, 28 October 2004

Revision as of 14:54, 28 October 2004

Line 40:

==Implementations==

===[[C programming language|C]]===

#define INFINITY ((int) pow(2, sizeof(int)*8-2)-1)

typedef struct

{

int source;

int dest;

int weight;

}Edge;

void BellmanFord(Edge edges[], size_t edgecount, size_t nodecount, size_t source) // nodecount = number of vertices

#define INFINITY ((int) pow(2, sizeof(int)*8-2)-1)

{

typedef struct

int* distance = (int*) malloc(nodecount*sizeof(int));

{

for(int i = 0; i < nodecount; i++)

int source;

{

int dest;

if(i == source) distance[i] = 0;

int weight;

else distance[i] = INFINITY;

}Edge;

}

for(int i = 0; i < nodecount; i++)

void BellmanFord(Edge edges[], size_t edgecount, size_t nodecount, size_t source) // nodecount = number of vertices

{

for(int ij = 0; ij < nodecountedgecount; ij++)

int* distance = (int*) malloc(nodecount*sizeof(int));

{

for(int i = 0; i < nodecount; i++)

if(distance[edges[j].dest] => distance[edges[j].source] + edges[j].weight;)

{

{

if(i == source) distance[i] = 0;

distance[edges[j].dest] = distance[edges[j].source] + edges[j].weight;

else distance[i] = INFINITY;

}

}

}

for(int i = 0; i < nodecount; i++)

}

{

for(int ji = 0; ji < edgecount; ji++)

{

if(distance[edges[ji].dest] > distance[edges[ji].source] + edges[ji].weight)

{

printf("Error occured. Negative edge weight cycles detected");

distance[edges[j].dest] = distance[edges[j].source] + edges[j].weight;

}break;

}

}

for(int i = 0; i < edgecountnodecount; i++)

{

ifprintf("The shortest distance[edges[ between nodes %i].dest] >and distance[edges[%i]. is %i", source], +i, edgesdistance[i].weight);

{}

}

printf("Error occured. Negative edge weight cycles detected");

break;

}

}

for(int i = 0; i < nodecount; i++)

{

printf("The shortest distance between nodes %i and %i is %i", source, i, distance[i]);

}

}

== Applications in routing ==