0.7 Graphs  (Page 15/21)

When i equals the number of vertices in the graph, each path will be the shortest path overall, unless there are negative-weight cycles. If a negative-weight cycle exists and is accessible from the source, then given any walk, a shorter one exists, so there is no shortest walk. Otherwise, the shortest walk will not include any cycles (because going around a cycle would make the walk shorter), so each shortest path visits each vertex at most once, and its number of edges is less than the number of vertices in the graph.

Applications in routing

A distributed variant of Bellman–Ford algorithm is used in distance-vector routing protocols, for example the Routing Information Protocol (RIP). The algorithm is distributed because it involves a number of nodes (routers) within an Autonomous system, a collection of IP networks typically owned by an ISP. It consists of the following steps:

1. Each node calculates the distances between itself and all other nodes within the AS and stores this information as a table.
2. Each node sends its table to all neighboring nodes.
3. When a node receives distance tables from its neighbors, it calculates the shortest routes to all other nodes and updates its own table to reflect any changes.

The main disadvantages of Bellman–Ford algorithm in this setting are

• Does not scale well
• Changes in network topology are not reflected quickly since updates are spread node-by-node.
• Counting to infinity (if link or node failures render a node unreachable from some set of other nodes, those nodes may spend forever gradually increasing their estimates of the distance to it, and in the meantime there may be routing loops)

Implementation

The following program implements the Bellman–Ford algorithm in C.

#include<limits.h>

#include<stdio.h>

#include<stdlib.h>

/* Let INFINITY be an integer value not likely to be

confused with a real weight, even a negative one. */

#define INFINITY ((1<<14)-1)

typedef struct {

int source;

int dest;

int weight;

} Edge;

void BellmanFord(Edge edges[], int edgecount, int nodecount, int source)

{

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

int i, j;

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

distance[i] = INFINITY;

/* The source node distance is set to zero. */

distance[source] = 0;

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

for (j=0; j<edgecount; j++) {

if (distance[edges[j].source]!= INFINITY) {

int new_distance = distance[edges[j].source]+ edges[j].weight;

if (new_distance<distance[edges[j].dest])

distance[edges[j].dest]= new_distance;

}

}

}

for (i=0; i<edgecount; i++) {

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

puts("Negative edge weight cycles detected!");

free(distance);

return;

}

}

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

printf("The shortest distance between nodes %d and %d is %d\n",

source, i, distance[i]);

}

free(distance);

return;

}

int main(void)

{

/* This test case should produce the distances 2, 4, 7, -2, and 0. */

Edge edges[10] = {{0,1, 5}, {0,2, 8}, {0,3, -4}, {1,0, -2},

{2,1, -3}, {2,3, 9}, {3,1, 7}, {3,4, 2},

{4,0, 6}, {4,2, 7}};

BellmanFord(edges, 10, 5, 4);