图论 迪杰斯特拉dijkstra求最短路径

这个测试用的是下面这个图：

9 16
0 1 2 3 4 5 6 7 8
0 1 1
0 2 5
1 2 3
1 4 5
1 3 7
2 4 1
2 5 7
3 4 2
3 6 3
4 6 9
4 5 3
4 7 9
5 7 5
6 7 2
6 8 7
7 8 4

运行结果如下：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<cmath>
#define inf 65535
#include<algorithm>
typedef struct Graph
{
    int vertex[100];
    int arc[100][100];
    int num_ver,num_edge;
} Mygraph;
void create(Mygraph *g)//建图
{
    int i,j,tmp,a,b,c;
    scanf("%d%d",&g->num_ver,&g->num_edge);//输入结点数和边数
    for(i=0; i<g->num_ver; i++)//输入结点集
        scanf("%d",&g->vertex[i]);

    for(i=0; i<g->num_ver; i++)//边的权值初始化
    {
        for(j=0; j<g->num_ver; j++)
            g->arc[i][j]=inf;
    }
    for(i=0; i<g->num_edge; i++)//输入边的权值
    {
        scanf("%d%d%d",&a,&b,&c);
        g->arc[a][b]=c;
        g->arc[b][a]=c;
    }
}
void ShortPath(Mygraph *g,int x)
{
    int i,j,k,tmp,Min;
    int adjver[100];
    int final[100];
    int sum=0;
    memset(final,0,sizeof(final));
    int lowcost[100];
    final[x]=1;

    //其实这个算法跟prime算法实现很相似，制作了一些很小的改动
    //就新增了一个final数组，用来记录这个点是够走过，如果走过就不再走，因为如果记录final[k]=1，那么
    //就是认为到达k点最短路径就是当前的样子，不能是其他的

    for(i=0; i<g->num_ver; i++)
    {
        lowcost[i]=g->arc[x][i];
        adjver[i]=x;
    }
    lowcost[x]=0;
    for(i=0; i<g->num_ver; i++)
    {
        Min=inf;//Min用来找最小的边权值
        j=0;
        while(j<g->num_ver)
        {
            if(!final[j]&&lowcost[j]<Min)
            {
                Min=lowcost[j];
                k=j;
            }
            j++;
        }
        //现在k里存的是从当前以选择结点出发可以到达的最近的结点(即边权值最小)
        final[k]=1;
        for(j=0; j<g->num_ver; j++)
        {

            if(!final[j]&&Min+g->arc[k][j]<lowcost[j])
            {
                lowcost[j]=Min+g->arc[k][j];
                adjver[j]=k;
            }
        }
    }
    printf("adjver[]:
");
    for(i=0; i<g->num_ver; i++)
        printf("%3d ",adjver[i]);
    puts("");
    printf("lowvost[]:
");
    for(i=0; i<g->num_ver; i++)
        printf("%3d ",lowcost[i]);
    puts("");

    /*打印0到8的路径*/
    /*
    int ans[10];
    int temp=8,cout_ans=0;
    ans[cout_ans++]=8;
    while(adjver[temp]!=0){
        ans[cout_ans++]=adjver[temp];
        temp=adjver[temp];
    }
    ans[cout_ans++]=0;
    for(i=cout_ans-1;i>=0;i--)
        printf("%d ",ans[i]);
    printf("
");
    */

}


int main()
{
    int i,j,k,x,y,z;
    Mygraph G;
    printf("第一次测验
");
    create(&G);
    ShortPath(&G,1);
    printf("第二次测验
");
    create(&G);
    ShortPath(&G,0);

    return 0;
}
/*
5 6
0 1 2 3 4
0 1 9
0 2 2
0 4 6
1 2 3
2 3 5
3 4 1

9 16
0 1 2 3 4 5 6 7 8
0 1 1
0 2 5
1 2 3
1 4 5
1 3 7
2 4 1
2 5 7
3 4 2
3 6 3
4 6 9
4 5 3
4 7 9
5 7 5
6 7 2
6 8 7
7 8 4
*/