路由器的Distance Vector算法
为什么当链路中的cost发生变大时，链路会出现选路环路？？？
写了下路由器的Link State算法,也就是Dijkstra最短路径算法，程序从
E:\\matrix.txt中读取矩阵,矩阵要指定大小，如6*6的矩阵
数据为
0 2 5 10000 10000 12 0 3 10000 10000 25 3 0 5 1 310000 10000 5 0 2 1000010000 10000 1 2 0 11 2 3 10000 1 0
#ifndef MATRIX_HPP#define MATRIX_HPP#include<iostream>using namespace std;typedef pair<int,int> Point;template<class T>class Matrix{private: T* start; int row;//行数 int col;//列数 public: Matrix(){ start=NULL;row=0;col=0; } Matrix(Matrix<T>& m){//拷贝操作 row=m.getRow();col=m.getCol(); start=new T[row*col]; for(int i=0;i<row;i++){ for(int j=0;j<col;j++){ set(i,j,m.get(i,j)); } } } Matrix(int i,int j){//构造i*j的matrix start = new T[i*j]; row=i;col=j; } int getRow(){return row;}//获取行数 int getCol(){return col;}//获取列数 void init(T t){//用t初始化 T* p=start; for(int i=0;i<row*col;i++){ *p++=t; } } T get(int i,int j){return start[i*col+j];}//获取i行j列的数 void set(int i,int j,Matrix<T>& m){//设置 i行j列 处 的该块 矩阵为m if(m.getCol()+j>this->col){ cout<<"size error\n"; return; } if(m.getRow()+i>this->row){ cout<<"size error\n"; return ; } for(int k=i;k<i+m.getRow();k++){ for(int l=j;l<j+m.getCol();l++){ set(k,l,m.get(k-i,l-j)); } } } void set(T t){//设置4个顶角的值 set(0,0,t);set(0,col-1,t);set(row-1,0,t);set(row-1,col-1,t); } void set(int i,int j,T t){//设置i,j处为t start[i*col+j]=t; } friend ostream& operator<<(ostream& o,Matrix<T>& m){//输出m m.print(o); return o; } void print(ostream& o){ for(int i=0;i<row;i++){ for(int j=0;j<col;j++){ o<<get(i,j)<<" "; } o<<endl; } } ~Matrix(){ delete []start; } Matrix<T> operator*(Matrix<T>& m){//矩阵乘法 if(col!=m.row){cout<<"error ! matrix's col isn't equal the second matrix's row\n";exit(0);} Matrix<T> result(row,m.col); for(int i=0;i<row;i++){ for(int j=0;j<m.col;j++){ T acc=T(); for(int k=0;k<col;k++){ acc+=get(i,k)*m.get(k,j); } result.set(i,j,acc); } } return result; } Point find(T t){//查找t的位置 Point* p=new Point; for(int i=0;i<row;i++){ for(int j=0;j<col;j++){ if(get(i,j)==t){ p->first=i;p->second=j; } } } return *p; } Matrix& operator=(Matrix<T>& m){//赋值操作 delete []start; row=m.getRow(); col=m.getCol(); start=new T[row*col]; for(int i=0;i<row;i++){ for(int j=0;j<col;j++){ set(i,j,m.get(i,j)); } } return *this; } friend istream& operator>>(istream& i,Matrix<T>& m){ m.input(i); return i; } void input(istream& i){ for(int j=0;j<row*col;j++){ i>>start[j]; } } };#endif#include"matrix.h"#include<iostream>#include<fstream>#include<vector>#include<stack>using namespace std;void show_path(int* D,int* pre,int n){ for(int i=1;i<n;i++){ //对于每个点 输出最短路径的值 并根据前驱结点输出整条路径 stack<int> path;while(!path.empty()){path.pop();} cout<<"length is:"<<D[i]<<endl;; cout<<"path is:"; int temp=i; while(pre[temp]!=-1){ path.push(temp); temp=pre[temp]; } cout<<"0"; while(!path.empty()){ cout<<"-"<<path.top(); path.pop(); } cout<<endl; }}vector<int>::iterator find_least(int* a,int n,vector<int>& v){ vector<int>::iterator log=v.begin();int min=10000; for(vector<int>::iterator it=v.begin();it!=v.end();it++){ if(min>a[*it]){min=a[*it];log=it;} } return log;}int main(){ fstream f; f.open("E:\\matrix.txt"); int N;cout<<"graph has dots:"<<endl;cin>>N; Matrix<int> m(N,N); f>>m;cout<<"the weght between the point is\n"<<m<<endl;//初始化邻接matrix vector<int> domain(N-1);//集合domain for(int i=0;i<N-1;i++){domain[i]=i+1;} //初始化 D[i]为0到i的最小值 pre[i]为i的前一个节点 int* D=new int[N];D[0]=0; int* pre=new int[N];pre[0]=-1; for(int i=1;i<N;i++){ D[i]=m.get(0,i); } for(int i=1;i<N;i++){ pre[i]=0; } //当domain不为空时，找domain中有最小值的nowpointer，将其从domain中去除， //更新domain中其他节点的最小值为D[current]=min{D[now_pointer]+c(now_pointer),D[current]} while(!domain.empty()){ vector<int>::iterator it=find_least(D,N,domain); int now_pointer=*it; domain.erase(it); for(vector<int>::iterator i=domain.begin();i!=domain.end();i++){ if(D[now_pointer]+m.get(now_pointer,*i)<D[*i]){ D[*i]=D[now_pointer]+m.get(now_pointer,*i); pre[*i]=now_pointer; } } } show_path(D,pre,N);//展示路径 f.close(); system("pause"); return 0;}