A função abaixo recebe um grafo g com comprimentos não-negativos nos arcos e um vértice r e devolve um caminho de comprominto mínimo de r a v para cada vértice v do grafo.
#define dist z.I
#define estado y.I
#define pred x.V
/* Interface para a fila com prioridades */
void init_queue (long d);
/*
* cria uma fila de vértices vazia em que todas as prioridades
* são pelo menos d
*/
void enqueue (Vertex *v, long d);
/*
* insere o vértice v com prioridade d na fila
*/
void requeue (Vertex *v, long d);
/*
* recebe um vértice que já está na fila e altera a sua prioridade
* para d. Supõem-se que no momento da chamada vale que
* a prioridade de v é maior que d.
*/
Vertex *del_min();
/*
* remove da fila o vértice com menor prioridade e devolve
* o endereço dessoe vértice.
*/
Boolean fila_vazi();
/*
* devolve TRUE se a fila com prioridades estiver vazia, em caso
* contrário devolve FALSE.
*/
void
dijkstra (Graph *g, Vertex *r)
{
Vertex *v0 = g->vertices;
Vertex *vn = g->vertices + g->n;
Vertex *v;
for (v = v0; v < vn; v++)
{
v->estado = NAOVISTO;
v->dist = infinito;
v->pred = v;
}
r->estado = VISITADO;
init_queue(0);
enqueue(r,0);
while (fila_vazia() == FALSE)
{
Vertex *u = del_min();
Arc *a;
for (a = u->arcs; a; a->next)
{
Vertex *v = a->tip;
long d = u->dist + a->len;
if (v->estado == NAOVISTO)
{
v->estado = VISITADO;
v->pred = u;
enqueue(v,d);
}
else if (v->dist > d)
{
v->pred = u;
requeue(v,d);
}
}
u->estado = EXAMINADO;
}
}