1.c语言编写路线

c语言编写路线

       #include <stdio.h>

       #include <malloc.h>

       #include<stdlib.h>

       #define MAX

       #define MAXNUM

       int previous[MAX-1];// 求路径需要

       int pp[MAX-1];// 记录最短路径

       typedef struct graphnode

       {

        int vexnum; //顶点

        int arcnum; //弧

        int gra[MAX][MAX]; //邻接矩阵表示0或1

       }Graph;

       int dist[MAX]; // 最短距离

       int arc[MAX][MAX]; // 权

       int main()

       {

        void Dijkstra(Graph *g,源码泊众源码int v);

        int i,j,n,m;

        int v; //源点

        Graph *G;

        G=(Graph *)malloc(sizeof(Graph));

        printf("vexnum:\n");

        scanf("%d",&G->vexnum);

        printf("arcnum:\n");

        scanf("%d",&G->arcnum);

        printf("graph:\n");

        for(i=0;i<G->vexnum;i++)

        for(j=0;j<G->vexnum;j++)

        {

        scanf("%d",&G->gra[i][j]);

        }

        for(i=0;i<G->vexnum;i++)

        for(j=0;j<G->vexnum;j++)

        {

        if(G->gra[i][j]==1)

        {

        printf("请输入%d到%d的权值:",i,j);

        scanf("%d",&arc[i][j]);//若有弧 则输入i到j直接的权

        }

        else

        arc[i][j]=MAXNUM;

        }

        printf("请输入源点v的值:");

        scanf("%d",&v);

        Dijkstra(G,v);

        printf("请输入源点所要到达的点：\n");

        scanf("%d",&n);

        pp[0]=0;

        i=1;

        m=n;// 记录n的值

        while(n!=0)// 求0到其他点路径

        {

        pp[i]=previous[n];

        i++;

        n=previous[n];

        }

        printf("Path:0 -> ");

        for(j=G->vexnum-1;j>=0;j--)

        if(pp[j]!=0)

        printf(" %d -> ",pp[j]);

        printf("%d\n",m);

        return 0;

       }

       void Dijkstra(Graph *G,int v)

       {

        int previous[MAX-1];

        int newdist;

        bool sign[MAX];

        if(v<0||v>MAX-1)

        {

        printf("该源点不存在！\n");

        return;

        }

        for(int i=0;i<G->vexnum;i++) //初始化

        {

        dist[i]=arc[v][i];

        sign[i]=false;

        if(dist[i]==MAXNUM)

        previous[i]=0;

        else

        previous[i]=v;

        }

        dist[v]=0;

        sign[v]=true;

        for(i=0;i<G->vexnum;i++) // i<n-1 待定

        {

        float temp=MAXNUM;

        int u=v; //u 中间变量

        for(int j=0;j<G->vexnum;j++)

        if((!sign[j])&&(dist[j]<temp))

        {

        u=j;

        temp=dist[j];

        }

        sign[u]=true;

        for(j=0;j<G->vexnum;j++)

        if((!sign[j])&&(arc[u][j]<MAXNUM))

        {

        newdist=dist[u]+arc[u][j];

        if(newdist<dist[j])

        {

        dist[j]=newdist;

        previous[j]=u;

        }

        }

        }

        for(i=0;i<G->vexnum;i++)

        if(dist[i]!=MAXNUM)

        printf("从%d到%d的最短路径是 %d\n",v,i,dist[i]);

        else

        printf("从%d到%d无最短路径\n",v,i);

        printf("\n");

       }

       è¿™æ˜¯Dijkstra算法求单源最短路径算法 上程序中 假定顶点从0开始，搜索整个图，然后求出0到其他各点的最短距离，存放在dist数组中，main函数后面几行是求0到其他各点的路径 基本上能满足你的要求了