The following algorithm is used to initialise a table structure for #202204141149 in order to store current calculated information.
The following table visualises a completed table:
| v | Known | \(d_v\) | \(p_v\) |
|---|---|---|---|
| \(v_1\) | 1 | 0 | 0 |
| \(v_2\) | 1 | 2 | \(v_1\) |
| \(v_3\) | 1 | 3 | \(v_4\) |
| \(v_4\) | 1 | 1 | \(v_1\) |
| \(v_5\) | 1 | 3 | \(v_4\) |
| \(v_6\) | 1 | 6 | \(v_7\) |
| \(v_7\) | 1 | 5 | \(v_4\) |
typedef int Vertex;
struct TableEntry {
List Header; // Adjacency List
int Known;
DistType Dist;
Vertex Path;
};
// Vertices are numbered from 0
#define NotAVertex (-1)
typedef struct TableEntry Table[NumVertex];void InitTable(Vertex Start, Graph G, Table T)
{
int i;
ReadGraph(G, T);
for (i = 0; i < NumVertex; i++) {
T[i].Known = False;
T[i].Dist = Infinity;
T[i].Path = NotAVertex;
}
T[Start].Dist = 0;
}
/**
* Print shortest path to V after algorithm has run
* Assume that the path exists
*/
void PrintPath(Vertex V, Table T)
{
if (TV].Path != NotAVertex) {
PrintPath(T[V].Path, T);
printf(" to");
}
printf("%v", V);
}