计算机网络实验4 编程实现路由算法

#include <stdlib.h> #include<iostream> #include<stdio.h> using namespace std; #define INFINITY 9999 #define MAX 10 void dijkstra(int G[MAX][MAX],int n,int startnode)//n为顶点个数 { int cost[MAX][MAX],distance[MAX],pred[MAX]; int visited[MAX],count,mindistance,i,j; //pred[] 记录前驱结点 //count记录已经找到最短路径的结点个数 visited[]标记到该点是否已找到最短路径，1为已找到 //设置权值 for(i=0;i<n;i++) for(j=0;j<n;j++) if(G[i][j]==0) cost[i][j]=INFINITY; else cost[i][j]=G[i][j]; //初始化 pred[],distance[],visited[] for(i=0;i<n;i++) { distance[i]=cost[startnode][i];///distance是开始结点到每个顶点的距离 pred[i]=startnode; visited[i]=0; } distance[startnode]=0; visited[startnode]=1; count=1; while(count<n-1) { mindistance=INFINITY; int u = startnode;// 找出当前未使用的点j的dist[j]最小值 for(int j=1; j<=n; ++j) if(visited[j]==0 && distance[j]<mindistance) { u = j; // u保存当前邻接点中距离最小的点的号码 mindistance = distance[j]; } visited[u]=1 ; for(int j=1; j<=n; j++) if( visited[j]==0 && cost[u][j]<INFINITY)//如果该点还没有找到最短路径，且和u点之间可达 { if(distance[u] + cost[u][j] < distance[j]) //在通过新加入的u点路径找到离v0点更短的路径 { distance[j] = distance[u] + cost[u][j]; //更新distance pred[j] = u; //记录前驱顶点 } } count++; } //输出路径和结点 for(i=0;i<n;i++) if(i!=startnode) { printf("\n结点%d和结点%d之间的最小距离是%d",startnode,i,distance[i]); printf("\n路径：%d",i); j=i; do { j=pred[j]; printf("<-%d",j); }while(j!=startnode); printf("\n"); } } int main() { int n,m;//顶点个数 int G[MAX][MAX]; int i,j; cout<<"请输入结点数量："<<endl; cin>>n; cout<<"请输入开始的结点："<<endl; cin>>m; for(i=0;i<n;i++) for(j=0;j<n;j++) G[i][j]=rand()%50; cout<<"结点之间的距离关系（结点1 结点2 距离）为："<<endl; for(i=0;i<n;i++) for(j=0;j<n;j++) cout<<i<<" "<<j<<" "<<G[i][j]<<endl; dijkstra(G,n,m);//G为带权无向图，n为顶点个数，0为开始结点 system("pause"); return 0; }