Mastering Algorithms With C - Kyle Loudon [206]
if (match(pth_vertex, adj_vertex)) {
/*****************************************************************
* *
* Relax the adjacent vertex in the list of adjacency-list *
* structures. *
* *
*****************************************************************/
relax(adjlist->vertex, pth_vertex, adj_vertex->weight);
}
}
}
/**************************************************************************
* *
* Prepare to select the next vertex. *
* *
**************************************************************************/
i++;
}
/*****************************************************************************
* *
* Load the vertices with their path information into a list. *
* *
*****************************************************************************/
list_init(paths, NULL);
for (element = list_head(&graph_adjlists(graph)); element != NULL; element =
list_next(element)) {
/**************************************************************************
* *
* Load each black vertex from the list of adjacency-list structures. *
* *
**************************************************************************/
pth_vertex = ((AdjList *)list_data(element))->vertex;
if (pth_vertex->color == black) {
if (list_ins_next(paths, list_tail(paths), pth_vertex) != 0) {
list_destroy(paths);
return -1;
}
}
}
return 0;
}
Shortest Paths Example: Routing Tables
One application in which shortest paths play an important role is routing data between networks in an internet. Routing is the process of making informed decisions about how to move data from one point to another. In an internet, this is accomplished by propagating small sections of the data, or packets , along interconnected points called gateways. As each packet passes through a gateway, a router looks at where the packet eventually needs to go and decides to which gateway it should be sent next. The goal of each router is to propagate a packet closer and closer to its final destination.
In order to propagate a packet closer to its destination, each router maintains information about the structure, or topology , of the internet. It stores this information in a routing table. A routing table contains one entry for each gateway the router knows how to reach. Each entry specifies the next gateway to which packets destined for another gateway should be sent.
So that packets are continually sent along the best route possible, routers periodically update their routing tables to reflect changes in the internet. In one type of routing, called shortest path first routing, or SPF routing, every router maintains its own map of the internet so that it can update its routing table by computing shortest paths between itself and other destinations. Its map is a directed, weighted graph whose vertices are gateways and whose edges are connections between the gateways. Each edge is weighted by the performance most recently observed for a connection. From time to time, routers exchange information about topology and performance using a protocol designed especially for this purpose.
Example 16.4 is a function, route, that computes the information necessary to update one entry in a routing table using SPF routing. The function accepts the list of path information returned in the paths argument of shortest. It uses this information to determine to which gateway a router should send a packet next to reach its destination most effectively.
To complete an entire table for a specific gateway, we first call shortest with the gateway passed as start. Next, for each destination to be included in the routing table, we call route with the destination passed as destination. We pass the same function for match as was provided to graph_init for the graph from which paths was generated. The route function follows parent pointers in paths from the destination back to the gateway and returns the best choice for moving a packet closer to its destination in next. The vertex returned in next points to