dijkstra.txt

用邻接表表示的数据结构

#include <stdio.h>
#define INFINITY 1000
typedef struct Vertex_Info
{
    int visited;
    int dist;
    int path;
}Vertex_Info;
typedef struct Vertex
{
    int vertex;
    int dist;
    struct Vertex *next;
}Vertex;
Vertex *graph;
int vertex_number;
Vertex_Info *vertex_info;
void readgraph(FILE *fp)
{
    int i,j;
    Vertex *new_vertex,*link;
    int dist;
    fscanf(fp,"%d",&vertex_number);
    graph=(Vertex*)malloc(sizeof(Vertex)*vertex_number);
    vertex_info=(Vertex_Info*)malloc(sizeof(Vertex_Info)*vertex_number);
    for(i=0;i<vertex_number;i++)
    {
        graph[i].vertex=i;
        graph[i]. dist=0;
        link=&graph[i];
        for(j=0;j<vertex_number;j++)
        {
            fscanf(fp,"%d",&dist);
            if((dist==-1)||(dist==0))
                continue;
            else
            {
                new_vertex=(Vertex*)malloc(sizeof(Vertex));
                new_vertex->vertex=j;
                new_vertex->dist=dist;
                new_vertex->next=NULL;
                link->next=new_vertex;
                link=link->next;
            }
        }
        link->next=NULL;
    }
}
void dijkstra_path(int start_vertex)
{
    int v,w;
    int i,min_dist;
    Vertex *link;
    for(i=0;i<vertex_number;i++)
    {
        vertex_info[i].visited=0;
        vertex_info[i].dist=INFINITY;
        vertex_info[i].path=-1;
    }
    vertex_info[start_vertex].dist=0;
    for(;;)
    {
        min_dist=INFINITY;
        for(i=0;i<vertex_number;i++)
        {
            if((vertex_info[i].visited==0)&&(vertex_info[i].dist<min_dist))
            {
                min_dist=vertex_info[i].dist;
                v=i;
            }
        }
        if(min_dist==INFINITY)/**//*it doesn't update*/
            break;
        vertex_info[v].visited=1;
        link=graph[v].next;
        while(link!=NULL)
        {
            w=link->vertex;
            if(vertex_info[w].visited==0)
            {
                if(vertex_info[w].dist>vertex_info[v].dist+link->dist)
                {
                    vertex_info[w].dist=vertex_info[v].dist+link->dist;
                    vertex_info[w].path=v;
                }/**//*update the shortest dist*/
            }
            link=link->next;
        }/**//*end check the adjacent vertex*/
    }/**//*end for*/
}
void print_graph()
{
    int i,j;
    Vertex *link;
    printf("Print Graph ");
    for(i=0;i<vertex_number;i++)
    {
        printf("%d: ",graph[i].vertex);
        link=graph[i].next;
        while(link!=NULL)
        {
            printf("%d ",link->vertex);
            link=link->next;
        }
        printf(" ");
    }
}
void print_path()
{
    int i;
    printf("Print Path ");
    for(i=0;i<vertex_number;i++)
        printf("%d    dist:%d    path:%d ",i,vertex_info[i].dist,vertex_info[i].path);
}
void freegraph()
{
    int i,j;
    Vertex *link1,*link2;
    for(i=0;i<vertex_number;i++)
    {
        link1=graph[i].next;
        while(link1!=NULL)
        {
            link2=link1->next;
            free(link1);
            link1=link2;
        }
    }
    free(graph);
    free(vertex_info);
}
int main(int argc, char *argv[])
{
    FILE *fp;
    fp=fopen("graph.txt","r");
    readgraph(fp);
    fclose(fp);
    dijkstra_path(0);
    print_graph();
    freegraph();
    print_path();
    getchar();
    return 0;
}