The world’s Largest Sharp Brain Virtual Experts Marketplace Just a click Away
Levels Tought:
Elementary,Middle School,High School,College,University,PHD
| Teaching Since: | Apr 2017 |
| Last Sign in: | 103 Weeks Ago, 3 Days Ago |
| Questions Answered: | 4870 |
| Tutorials Posted: | 4863 |
MBA IT, Mater in Science and Technology
Devry
Jul-1996 - Jul-2000
Professor
Devry University
Mar-2010 - Oct-2016
I need help finishing a program that computes the forwarding tables in a network using Dijkstra's Shortest Path Algorithm..... here is what I have so far (see parts marked to do)
Â
#include <climits>
#include <iostream>
using namespace std;
#define N 100
enum LabelState {TEMP, FINAL};
struct Label {
int p;
int d;
LabelState st;
};
int Dist[N][N];
Label label[N];
void InitDist(int n)
{
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
Dist[i][j] = INT_MAX;
}
void InitLabels(int n)
{
for (int i = 0; i < n; ++i) {
label[i].p = -1;
label[i].d = INT_MAX;
label[i].st = TEMP;
}
}
int ReadNetwork()
{
int n;
int i, j, d;
cin >> n;
InitDist(n);
while (cin >> i >> j >> d) {
Dist[i][j] = Dist[j][i] = d;
}
return n;
}
int FindMinTempLabel(int n)
{
// TO DO: Among all vertices whose labels are still in the TEMP state, return one with the smallest d.
}
void Dijkstra(int n, int v)
{
InitLabels(n);
label[v].d = 0;
int num_temp = n;
while (num_temp > 0) {
int u = FindMinTempLabel(n); // Find vertex u with smallest TEMP label.
// TO DO: Set state of label[u] to FINAL, Decrement num_temp,
// and scan row u of Dist matrix, updating the labels of TEMP neighbors of u if needed.
}
}
void PrintLabels(int n)
{
for (int u = 0; u < n; ++u) {
cout << u << " " << label[u].p << " " << label[u].d << endl;
}
}
int NextHop(int v, int w)
{
// TO DO: Return the next hop from v to reach destination w.
}
void PrintForwardingTable(int n, int v)
{
// TO DO: Print the forwarding table for router v.
}
int main()
{
int n = ReadNetwork();
// TO DO: Run Dijkstra n times with each vertex as the starting vertex, and print forwarding table
// for each of the routers represented by the vertices.
return 0;
}