最短路径.cpp

最短路径的问题

#include<stdio.h>
main()
{
    int s=0,r=0,k,l,a,i,j,m,n,c=0,x,y,count=0,start;
    printf("请依次输入顶点和边的个数:");
    scanf("%d %d",&n,&m);
    int u[n],v[n],t1[n];
    for(i=0;i<n;i++)
     {u[i]=v[i]=0;
      t1[i]=10240;}
    int tree[n][n];
    int t[n][n],sum[n][n];
    for(i=0;i<n;i++)
     for(j=0;j<n;j++)
      {
        tree[i][j]=0;
        t[i][j]=0;
        sum[i][j]=0;
      }
    printf("请输入各边的权:\n");
    for(r=0;r<m;r++)
     {
      scanf("%d %d %d",&i,&j,&x);
      tree[i][j]=x;
     }
    printf("请输入源点:");
    scanf("%d",&start);
    u[s]=start;
    for(i=0;i<n;i++)
     v[i]=i;
    v[start]=-1;
    printf("\n单源最短路径为:\n");
    while(s!=n-1)
     {
         for(k=0;k<=s;k++)
         {
            for(l=0;l<n;l++)
             {
              if(v[l]!=-1&&tree[u[k]][l]>0)
                 {
                  if(t1[count]>(sum[start][u[k]]+tree[u[k]][l]))
                   {
                    sum[start][l]=sum[start][u[k]]+tree[u[k]][l];
                    t1[count]=sum[start][u[k]]+tree[u[k]][l];
                    t[0][count]=u[k];
                    t[1][count]=l;
                   }
                 }
             }
         }
        if(t1[count]==10240) break;
        u[s+1]=t[1][count];
        v[t[1][count]]=-1;
        s++;
        printf("%d--%d\n",t[0][count],t[1][count]);
        count++;
     }
     printf("\n该源点到各点的最短路径的权依次为:\n");
     for(i=0;i<n;i++)
      {
        if(start!=i)
        {
           printf("到%d距离为:",i);
           if(sum[start][i]==0)
            printf("不可到达\n");
           else
            printf("%d\n",sum[start][i]);
        }
      }
}