#include #include using namespace std; const int INF = numeric_limits::max(); // Represents no known path int main() { int nodeCount; cout << "\n Enter Number of Nodes: "; cin >> nodeCount; // directDist[src][dst] = direct link cost between src and dst (INF if no direct link) int directDist[50][50]; for (int src = 0; src < nodeCount; src++) { for (int dst = 0; dst < nodeCount; dst++) { directDist[src][dst] = (src == dst) ? 0 : INF; } } // Assign node labels A, B, C, D, ... char nodeName[50]; for (int nodeIndex = 0; nodeIndex < nodeCount; nodeIndex++) { nodeName[nodeIndex] = 'A' + nodeIndex; } // Read direct link distances between each pair of nodes for (int src = 0; src < nodeCount; src++) { for (int dst = src + 1; dst < nodeCount; dst++) { int linkCost; cout << "\n Enter Distance between " << nodeName[src] << " - " << nodeName[dst] << " (use -1 for no connection): "; cin >> linkCost; if (linkCost != -1) { directDist[src][dst] = linkCost; directDist[dst][src] = linkCost; // Assume symmetric (undirected) links } } } // viaNode[src][dst] = intermediate node used on the current best path from src to dst int viaNode[50][50]; for (int src = 0; src < nodeCount; src++) for (int dst = 0; dst < nodeCount; dst++) viaNode[src][dst] = -1; // bestDist[src][dst] = best known shortest distance from src to dst int bestDist[50][50]; // --- Iterative Distance Vector update loop --- bool updated; do { updated = false; for (int src = 0; src < nodeCount; src++) { for (int dst = 0; dst < nodeCount; dst++) { bestDist[src][dst] = directDist[src][dst]; viaNode[src][dst] = src; // Default: reach dst directly from src // Try routing through each intermediate node k for (int via = 0; via < nodeCount; via++) { if (directDist[src][via] != INF && directDist[via][dst] != INF) { int candidateDist = directDist[src][via] + directDist[via][dst]; if (candidateDist < bestDist[src][dst]) { bestDist[src][dst] = candidateDist; viaNode[src][dst] = via; updated = true; } } } } } // Propagate the improved distances back into directDist for the next iteration for (int src = 0; src < nodeCount; src++) for (int dst = 0; dst < nodeCount; dst++) directDist[src][dst] = bestDist[src][dst]; } while (updated); // Repeat until no further improvements (convergence) // --- Print final routing tables --- cout << "\n After Convergence:"; for (int src = 0; src < nodeCount; src++) { cout << "\n\n" << nodeName[src] << " Routing Table"; cout << "\n Node\tDist\tVia"; for (int dst = 0; dst < nodeCount; dst++) { cout << "\n" << nodeName[dst] << "\t"; if (bestDist[src][dst] == INF) cout << "INF"; else cout << bestDist[src][dst]; cout << "\t"; if (src == viaNode[src][dst]) cout << "-"; // Direct connection, no intermediate hop else cout << nodeName[viaNode[src][dst]]; } } cout << "\n"; return 0; }