Content deleted Content added
m Fix link |
Jellyworld (talk | contribs) No edit summary |
||
Line 37:
The correctness of the algorithm follows from the lemma together with the observation that shortest path between any two vertices must contain at most ''V(G)'' edges. (If a path contained more than ''V(G)'' edges, it must contain some vertex ''v'' twice. Then, it can be shortened by removing the part between the first occurrence of ''v'' and the second occurrence. This means that it was not the shortest path.)
==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
{
int* distance = (int*) malloc(nodecount*sizeof(int));
for(int i = 0; i < nodecount; i++)
{
if(i == source) distance[i] = 0;
else distance[i] = INFINITY;
}
for(int i = 0; i < nodecount; i++)
{
for(int j = 0; j < edgecount; j++)
{
if(distance[edges[j].dest] > distance[edges[j].source] + edges[j].weight)
{
distance[edges[j].dest] = distance[edges[j].source] + edges[j].weight;
}
}
}
for(int i = 0; i < edgecount; i++)
{
if(distance[edges[i].dest] > distance[edges[i].source] + edges[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 ==
| |||