Mastering Algorithms With C - Kyle Loudon [205]
* *
*****************************************************************************/
static void relax(PathVertex *u, PathVertex *v, double weight) {
/*****************************************************************************
* *
* Relax an edge between two vertices u and v. *
* *
*****************************************************************************/
if (v->d > u->d + weight) {
v->d = u->d + weight;
v->parent = u;
}
return;
}
/*****************************************************************************
* *
* ------------------------------- shortest ------------------------------- *
* *
*****************************************************************************/
int shortest(Graph *graph, const PathVertex *start, List *paths, int (*match)
(const void *key1, const void *key2)) {
AdjList *adjlist;
PathVertex *pth_vertex,
*adj_vertex;
ListElmt *element,
*member;
double minimum;
int found,
i;
/*****************************************************************************
* *
* Initialize all of the vertices in the graph. *
* *
*****************************************************************************/
found = 0;
for (element = list_head(&graph_adjlists(graph)); element != NULL; element =
list_next(element)) {
pth_vertex = ((AdjList *)list_data(element))->vertex;
if (match(pth_vertex, start)) {
/***********************************************************************
* *
* Initialize the start vertex. *
* *
***********************************************************************/
pth_vertex->color = white;
pth_vertex->d = 0;
pth_vertex->parent = NULL;
found = 1;
}
else {
/***********************************************************************
* *
* Initialize vertices other than the start vertex. *
* *
***********************************************************************/
pth_vertex->color = white;
pth_vertex->d = DBL_MAX;
pth_vertex->parent = NULL;
}
}
/*****************************************************************************
* *
* Return if the start vertex was not found. *
* *
*****************************************************************************/
if (!found)
return -1;
/*****************************************************************************
* *
* Use Dijkstra's algorithm to compute shortest paths from the start vertex. *
* *
*****************************************************************************/
i = 0;
while (i < graph_vcount(graph)) {
/**************************************************************************
* *
* Select the white vertex with the smallest shortest-path estimate. *
* *
**************************************************************************/
minimum = DBL_MAX;
for (element = list_head(&graph_adjlists(graph)); element != NULL; element
= list_next(element)) {
pth_vertex = ((AdjList *)list_data(element))->vertex;
if (pth_vertex->color == white && pth_vertex->d < minimum) {
minimum = pth_vertex->d;
adjlist = list_data(element);
}
}
/**************************************************************************
* *
* Color the selected vertex black. *
* *
**************************************************************************/
((PathVertex *)adjlist->vertex)->color = black;
/**************************************************************************
* *
* Traverse each vertex adjacent to the selected vertex. *
* *
**************************************************************************/
for (member = list_head(&adjlist->adjacent); member != NULL; member =
list_next(member)) {
adj_vertex = list_data(member);
/***********************************************************************
* *
* Find the adjacent vertex in the list of adjacency-list structures. *
* *
***********************************************************************/
for (element = list_head(&graph_adjlists(graph)); element != NULL;
element = list_next(element)) {
pth_vertex