dijkstra is an implementation in C of the algorithm for finding the shortest path.
This is an extract with the actual algorithm:
/* Run Dijkstra's algorithm on the vertices
* Recomputes the values for all vertices
*/
void graph_dijkstra (struct vertex *start_vx) {
/* build the Q as 'vl' */
struct vertex_list *vl = graph_build_vlist(start_vx);
start_vx->value = 0; /* mark start value */
while (1) {
/* get the current shortest */
vlist_sort(vl);
struct vertex *u = vlist_pop_least(vl);
if (u == NULL) /* we reached last vertex */
break;
/* measure all edges and relax vertices */
for (int i = 0; i < u->n_edges; ++i) {
unsigned alt = u->value + u->edges[i].cost;
struct vertex *nv = u->edges[i].goal;
if (alt < nv->value) {
nv->value = alt;
nv->parent = u;
}
}
}
vlist_free(vl);
}