[prev] 18 [next]

Dijkstra's Algorithm (C implementation)

What's needed for real implementation?

#define MAX_WT  Value larger than any real weight
#define NO_EDGE Value in adj matrix to indicate no edge

// Priority Queue interface
// use dist[] array to determine PQ priorities
PQueue newPQ(float dist[], int nV);
// add vertex to priority queue
void join(PQueue, Vertex);
// remove vertex with smallest dist[]
Vertex leave(PQueue, Vertex);
// reorder queue based on change to vertex
void reorder(PQueue, Vertex);
// check whether queue is empty
int empty(PQueue);
// clean up queue data
void disposePQ(PQueue);