luyou.cpp

动态路由算法

#include"stdio.h"
#include"stdlib.h"


#define   Maxint   32767
#define maxsize 10

typedef int vertype;

int visited[100];                      /*访问标志向量定义为全局量*/

int num=0;

typedef struct{
    vertype data[maxsize+1];
    int arcs[maxsize][maxsize];
    int vernum,arcnum;
 }Graph;


/* 初始化图的邻接矩阵*/
void InintGraph(Graph &G)
{
    int i,j;
    int w;

    G.vernum = maxsize;
    G.arcnum = 0;


    for(i=1;i<=G.vernum;i++)
    {
    	G.data[i] = i;
	}



    for(i=0;i<G.vernum;i++)
      for(j=0;j<G.vernum;j++)
          G.arcs[i][j]=Maxint;


    for(i=1;i<=G.vernum;i++)
       G.arcs[i][i] = 0;

}


void Graph_increase(Graph &G,int node)
{
	int i,n;
	int v,w;

	
	printf("输入该顶点的邻居数：");
	scanf("%d",&n);
	
	 for(i=1;i<=n;i++)
	 {
	 	printf("输入第%d个邻居的信息(v,w)：",i);
        scanf("%d,%d",&v,&w);
        G.arcs[node][v]=w;
        G.arcs[v][node]=w;
	 	
	 }
}

void ShortestPath_DIJ(Graph &G,int v0,int Path[],int Dist[])
{
    int v,w,m,k,min;
    int RedDot[20];

    for(v=1;v<=G.vernum;v++)
    {
        if(v!=v0)
        {
            Dist[v]=G.arcs[v0][v];
            Path[v]=v0;
            RedDot[v]=0;
        } /*初始化*/
    }
    RedDot[v0]=1;

    for(v=1;v<=G.vernum;v++)
    {
        min=Maxint;
        for(k=1;k<=G.vernum;k++)
         {  if(!RedDot[k])
              if(Dist[k]<min) { m=k; min=Dist[k];}
           }
                                                /*寻找距当前点最短距离的点*/
         RedDot[m]=1;
         
        for(w=1;w<=G.vernum;w++)
        {
            if(G.arcs[m][w]&&RedDot[w]==0)
            {
                if(Dist[w]>Dist[m]+G.arcs[m][w])
                {
                   Dist[w]=Dist[m]+G.arcs[m][w];
                   Path[w]=m;
                }/* 对其他点是否有影响 */
            }/* 找一个黑点，并且存在边 */
        }
    }
}

main()
{
    Graph G;

    int i,j,k,m,w;
    int reverse[20];
    int Path[20];
    int Dist[20];
    
    
    InintGraph(G);
    printf("输入节点：");
    scanf("%d",&i);

    while(i!=0)
    {

        Graph_increase(G,i);
        num++;
        printf("输入节点：");
        scanf("%d",&i);
      } 	

    
    printf("输入要查找的节点：");
    scanf("%d",&i);

    ShortestPath_DIJ(G,i,Path,Dist);
    
   /*
   for(w=1;w<=num;w++)
    {
        if(i!=w){
        printf("%d\n",Path[w]); }

    }*/
    
    for(j=1;j<=G.vernum;j++)
    {
       if((j!=i)&&(Dist[j]<Maxint))
       {  printf("%d到%d的最短距离为:%d\n",i,j,Dist[j]);
       

                         m=1; k=j;
                         do
                         {

                            reverse[G.vernum-m]=Path[k];
                            k=Path[k];
                            m++;
                         }while(k!=i);

                         for(k=G.vernum-m+1;k<G.vernum;k++)
                         {
                            printf("%d-->",reverse[k]);

                         }
                         printf("%d\n",j);
            
       }//if
       
     }
	system("pause");
}