DV算法模拟，仅供参考

这周网络实验看着孩子们那么苦逼，我真是不忍心，不过还是有比较牛的孩子，老人家落后了啊。因为前几天比较忙，一直再搞论文的实验，所以也没亲自动手做一下，今天刚好有兴致，简单做一下吧，DV算法的简单模拟，没有动态加节点，还有一些问题没有考虑，代码略乱，仅供参考。

/*========================================================================
#   FileName: DV.cpp
#     Author: daweibalong
#      Email: [e-mail]
#   HomePage: 
# LastChange: 2012-11-25 18:50:27
#   编译环境:GCC
========================================================================*/
#include <iostream>
using namespace std;

#define Item_Max 20
#define Router_Max 20
//定义弧
struct ArcNode
{
	int adjex;//相邻节点标号
	int weight;
	struct ArcNode *nextArc;
};

//定义路由表
typedef struct Router
{
	int destination;
	int cost;
	int next_hop;
}RouterItem, RouterTable[Item_Max];

//定义路由节点
struct RouterNode
{
	int num;//节点标号
	int reachable_num;//可达节点的数目
	ArcNode *first;
	RouterTable rtable;
};

RouterNode rlist[Router_Max];//路由节点列表
RouterNode rlist_temp[Router_Max];//缓存状态，模拟并发
int router_num;//路由节点数量

//*****函数列表**********
void initRouters();//初始化路由节点及其路由表
int reachable(int, int);//考察第一个节点是否可达第二个节点， 与当前路由表状态有关
bool exchange(int);//制定标号的路由节点获取相邻路由的路由表信息，并根据情况进行路由表的修改
void DV();//循环执行所有路由的信息交换，直至收敛
void printRouterTable(int);//打印路由表
//***********************

//初始化路由节点及路由表
void initRouters()
{
	cout << "Please input the number of the routers:";
	cin >> router_num;

	int i, j;
	for (i =0; i < router_num; ++i)
	{
		rlist[i].num = i;
		rlist[i].reachable_num = 0;
		rlist[i].first = NULL;
	}
	int neighbors_num;
	cout << "now, tell each node of their neighbors and distance between them:" << endl;
	for (i = 0; i < router_num; ++i)
	{
		cout << "Router(" << i << "):" << endl;
		cout << "--the number of neighbors:";
		cin >> neighbors_num;
		cout << "----neighbor lable and distance:" << endl;
		for (j = 0; j < neighbors_num; ++j)
		{
			ArcNode *arc = new ArcNode;
			cout << "------neighbor" << j << ":" << endl;
			cout << "--------label:";
			cin >> arc->adjex;
			cout << "--------weight:";
			cin >> arc->weight;

			arc->nextArc = rlist[i].first;
			rlist[i].first = arc;
			
			rlist[i].rtable[j].destination = arc->adjex;
			rlist[i].rtable[j].cost = arc->weight;
			rlist[i].rtable[j].next_hop = arc->adjex;
		}
		rlist[i].reachable_num = neighbors_num;
	}
}

//判断node1号路由在目前路由表的情况下是否可达node2号路由
//不可达返回-1
//可达返回cost
int reachable(int node1, int node2)
{
	for (int i = 0 ; i < rlist[node1].reachable_num; ++i)
	{
		if (rlist[node1].rtable[i].destination == node2)
			return rlist[node1].rtable[i].cost;
	}
	return -1;
}

//第num个路由获取邻居节点的路由表并进行更新
bool exchange(int num)
{
	ArcNode *arc = rlist[num].first;
	bool change = false;
	while (arc != NULL)
	{
		int i;
		//get neighbor rtable
		for (i = 0; i < rlist[arc->adjex].reachable_num; ++i)
		{
			//遇见不可达节点，加入路由表
			if (num != rlist[arc->adjex].rtable[i].destination && reachable(num, rlist[arc->adjex].rtable[i].destination) == -1)
			{
				RouterItem item;
				item.destination = rlist[arc->adjex].rtable[i].destination;
				item.cost =rlist[arc->adjex].rtable[i].cost + arc->weight;
				item.next_hop = arc->adjex;

				rlist_temp[num].rtable[rlist[num].reachable_num] = item;
				rlist_temp[num].reachable_num ++;
				change = true;
			}
			else if (num != rlist[arc->adjex].rtable[i].destination)//遇见可达节点 比较距离 看是否更新路由表 
			{
				if (rlist[num].rtable[i].cost >rlist[arc->adjex].rtable[i].cost + arc->weight)
				{
					rlist_temp[num].rtable[i].cost =rlist[arc->adjex].rtable[i].cost + arc->weight;
					rlist_temp[num].rtable[i].next_hop = arc->adjex;
					change = true;
				}
			}
		}
		arc = arc->nextArc;
	}
	return change;
}

//打印单个路由的路由表
void printRouterTable (int num)
{
	cout << endl;
	cout << "--------Router:" << num << "---------" << endl;
	cout << "reachable_num:" << rlist[num].reachable_num << endl;
	cout << "des | next | cost" << endl;
	for (int i = 0; i < rlist[num].reachable_num; ++i)
	{
		cout << rlist[num].rtable[i].destination << "   |   " << rlist[num].rtable[i].next_hop << "  |  " << rlist[num].rtable[i].cost << endl;
	}
}

//DV算法，循环更新，直到收敛
void DV()
{
	int i, j = 0;
	while (true)
	{
		bool change = false;
		for (i = 0; i < router_num; ++i)
		{
			rlist_temp[i] = rlist[i];
		}

		for (i = 0; i < router_num; ++i)
		{
			change |= exchange(i);
		}
		if (change == false)
		{
			cout << "+++++++Converged!++++++++" << endl;
			break;
		}
		for (i = 0; i < router_num; ++i)
		{
			rlist[i] = rlist_temp[i];
		}
		
		cout << endl <<  "++++++Round " << ++j << "++++++++" << endl;
		for (i = 0; i < router_num; i++)
			printRouterTable(i);
	}
}

int main()
{
	initRouters();
	DV();
	return 0;
}