• Choose a category
• All
• Classic-Fiction

Figure 16.5a illustrates the computation of a routing table for a router at gw1 in the internet shown (modeled using a graph similar to the one in Figure 16.3). Figure 16.5b illustrates the computation of the routing table for a router at gw2 . Notice how the shortest paths are different depending on where we start in the internet. Also, notice that in Figure 16.5b there is no way to reach gw1, so there is no entry for it in the table.

Figure 16.5. Routing tables computed for gateways (a) gw1 and (b) gw2 , in an internet

The runtime complexity of route is O (n 2), where n is the number of gateways in paths. This is because we look up in paths the parent of each vertex between the destination we are interested in and the starting point in the internet. If the shortest path between us and the destination contains every gateway in paths, in the worst case we may have to search the list of gateways n times to find every parent.

Example 16.4. Implementation of a Function for Updating Entries in Routing Tables

/*****************************************************************************

* *

* -------------------------------- route.c ------------------------------- *

* *

*****************************************************************************/

#include

#include "graphalg.h"

#include "list.h"

#include "route.h"

/*****************************************************************************

* *

* --------------------------------- route

-------------------------------- *

* *

*****************************************************************************/

int route(List *paths, PathVertex *destination, PathVertex **next, int

(*match)(const void *key1, const void *key2)) {

PathVertex *temp,

*parent;

ListElmt *element;

int found;

/*****************************************************************************

* *

* Locate the destination in the list of gateways. *

* *

*****************************************************************************/

found = 0;

for (element = list_head(paths); element != NULL; element =

list_next(element)) {

if (match(list_data(element), destination)) {

temp = list_data(element);

parent = ((PathVertex *)list_data(element))->parent;

found = 1;

break;

}

}

/*****************************************************************************

* *

* Return if the destination is not reachable. *

* *

*****************************************************************************/

if (!found)

return -1;

/*****************************************************************************

* *

* Compute the next gateway in the shortest path to the destination. *

* *

*****************************************************************************/

while (parent != NULL) {

temp = list_data(element);

found = 0;

for (element = list_head(paths); element != NULL; element =

list_next(element)) {

if (match(list_data(element), parent)) {

parent = ((PathVertex *)list_data(element))->parent;

found = 1;

break;

}

}

/**************************************************************************

* *

* Return if the destination is not reachable. *

* *

**************************************************************************/

if (!found)

return -1;

}

*next = temp;

return 0;

}

Description of the Traveling-Salesman Problem

Imagine a salesman who needs to visit a number of cities as part of the route he works. His goal is to travel the shortest possible distance while visiting every city exactly once before returning to the point at which he starts. This is the idea behind the traveling-salesman problem.

In a graph, a tour in which we visit every other vertex exactly once before returning to the vertex at which we started is called a hamiltonian cycle. To solve the traveling-salesman problem, we use a graph G = (V, E ) as a model and look for the hamiltonian cycle with the shortest length. G is a complete,