Implement algorithm 18.2 (page 317), Dijkstra's algorithm as a C++, Java or Python program.

https://web.njit.edu/~bm245/IT420/Computer-Networks-and-Internets-Fifth-Edition.pdf

Given:

A graph with a nonnegative weight assigned to each edge and a designated source node

Compute:

The shortest distance from the source node to each other node and a next-hop routing table

Method:

Initialize set S to contain all nodes except the source node;

Initialize array D so that D[v] is the weight of the edge from the source to v if such an edge exists, and infinity otherwise;

Initialize entries of R so that R[v] is assigned v if an edge exists from the source to v, and zero otherwise;

while (set S is not empty) {

choose a node u from S such that D[u] is minimum;

if (D[u] is infinity) {

error: no path exists to nodes in S; quit;

}

delete u from set S;

for each node v such that (u,v) is an edge {

if (v is still in S) {

c = D[u] + weight(u,v);

if (c < D[v]) {

R[v] = R[u];

D[v] = c;

}

}

}

}

Algorithm 18.2 A version of Dijkstras algorithm that computes R, a nexthop forwarding table, and D, the distance to each node from the specified source node.