迪杰斯特拉算法

用个结构体存储一下。。。比较笨的方法。。。

#include <stdio.h>
#include <stdlib.h>
int n=8;

int cost[100][100];
 struct node{
    int data;
    int pre;
}Lnode[100];
void dijkstra(int v0,int v1)//dijkstra算法
{
    int s[100];
    int mindis,dis,i,j,u;
    for(i=1;i<=n;i++)
    {
        Lnode[i].data=cost[v0][i];
        s[i]=0;
    }
    s[v0]=1;
    for(i=1;i<=n;i++)
    {
        mindis=32676;
        for(j=1;j<=n;j++)
        {
            if(s[j]==0&&Lnode[j].data<mindis)
            {
                u=j;
                mindis=Lnode[j].data;
                if(Lnode[j].pre==0)
                    Lnode[j].pre=v0;
            }
        }
        s[u]=1;
        for(j=1;j<=n;j++)
        {
            if(s[j]==0)
            {
                dis=Lnode[u].data+cost[u][j];
                if(Lnode[j].data>dis)
                {
                    Lnode[j].data=dis;
                    Lnode[j].pre=u;
                }
                else
                {
                    Lnode[j].data=Lnode[j].data;
                }
            }
        }
        if(i==v1)
            break;
    }
    printf("%d到%d的最短距离：\n",v0,v1);
    printf("%d  ",Lnode[v1].data);
    while(1)
    {
        printf("%d ",Lnode[v1].pre);
        v1=Lnode[v1].pre;
        if(v1==v0)
            break;
   
    }printf("\n");
}

int main()
{
    int i,j,v0=1,v1=7,d;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            cost[i][j]=32676;
        }
    }
    for(i=1;i<=n;i++)
    {
        cost[i][i]=0;
    }
    cost[1][2]=20;cost[1][4]=50;cost[1][3]=30;
    cost[2][5]=40;cost[2][8]=30;cost[3][4]=40;
    cost[3][6]=20;cost[4][5]=20;cost[4][7]=90;
    cost[5][7]=60;cost[5][8]=70;cost[6][4]=30;
    cost[6][5]=100;cost[6][7]=80;cost[8][7]=150;
    dijkstra(v0,v1);
   
    return 0;
}
我试过了，应该可以！