Mastering Algorithms With C - Kyle Loudon [202]
mst_vertex = ((AdjList *)list_data(element))->vertex;
if (match(mst_vertex, adj_vertex)) {
/*****************************************************************
* *
* Decide whether to change the key value and parent of the *
* adjacent vertex in the list of adjacency-list structures. *
* *
*****************************************************************/
if (mst_vertex->color == white && adj_vertex->weight <
mst_vertex->key) {
mst_vertex->key = adj_vertex->weight;
mst_vertex->parent = adjlist->vertex;
}
break;
}
}
}
/**************************************************************************
* *
* Prepare to select the next vertex. *
* *
**************************************************************************/
i++;
}
/*****************************************************************************
* *
* Load the minimum spanning tree into a list. *
* *
*****************************************************************************/
list_init(span, 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. *
* *
**************************************************************************/
mst_vertex = ((AdjList *)list_data(element))->vertex;
if (mst_vertex->color == black) {
if (list_ins_next(span, list_tail(span), mst_vertex) != 0) {
list_destroy(span);
return -1;
}
}
}
return 0;
}
Description of Shortest Paths
Finding the shortest path, or minimum-weight path, from one vertex to another in a graph is an important distillation of many routing problems. Formally stated, given a directed, weighted graph G = (V, E ), the shortest path from vertex s to t in V is the set S of edges in E that connect s to t at a minimum cost.
When we find S, we are solving the single-pair shortest-path problem. To do this, in actuality we solve the more general single-source shortest-paths problem , which solves the single-pair shortest-path problem in the process. In the single-source shortest-paths problem, we compute the shortest paths from a start vertex s to all other vertices reachable from it. We solve this problem because no algorithm is known to solve the single-pair shortest-path problem any faster.
Dijkstra's Algorithm
One approach to solving the single-source shortest-paths problem is Dijkstra's algorithm (pronounced "Dikestra"). Dijkstra's algorithm grows a shortest-paths tree, whose root is the start vertex s and whose branches are the shortest paths from s to all other vertices in G. The algorithm requires that all weights in the graph be nonnegative. Like Prim's algorithm, Dijkstra's algorithm is another example of a greedy algorithm that happens to produce an optimal result. The algorithm is greedy because it adds edges to the shortest-paths tree based on which looks best at the moment.
Fundamentally, Dijkstra's algorithm works by repeatedly selecting a vertex and exploring the edges incident from it to determine whether the shortest path to each vertex can be improved. The algorithm resembles a breadth-first search because it explores all edges incident from a vertex before moving deeper in the graph. To compute the shortest paths between s and all other vertices, Dijkstra's algorithm requires that a color and shortest-path estimate be maintained with every vertex. Typically, shortest-path estimates are represented by the variable d.
Initially, we set all colors to white, and we set all shortest-path estimates to ∞, which represents an arbitrarily large value greater than the weight of any edge in the graph. We set the shortest-path estimate of the start vertex to 0. As the algorithm progresses, we assign to all vertices except the start vertex a parent in the shortest-paths tree. The parent of a vertex may change several times before the algorithm terminates.
Dijkstra's algorithm proceeds as follows. First, from among all