Chinaunix首页 | 论坛 | 博客
  • 博客访问: 969442
  • 博文数量: 128
  • 博客积分: 10012
  • 博客等级: 上将
  • 技术积分: 2050
  • 用 户 组: 普通用户
  • 注册时间: 2008-10-15 17:49
文章分类

全部博文(128)

文章存档

2011年(16)

2009年(57)

2008年(55)

分类:

2009-10-18 21:13:59

样例图:

输入格式:

输出格式:

输入时,将s,t,x,y,z五个点按照1,2,3,4,5起别名,输入格式按照下图例所示
当提示Please enter the vertex where Dijkstra algorithm starts:时输入算法的起始点
比如计算结果v1v4v2表示从点1到点2经过1,4,2为最短路径
Dijkstra算法的完整实现版本,算法的源代码
/* Dijkstra.c
 
    Copyright (c) 2002, 2006 by ctu_85
    All Rights Reserved.
*/
#include "stdio.h"
#include "malloc.h"
#define maxium 32767
#define maxver 9 /*defines the max number of vertexs which the programm can handle*/
#define OK 1
struct Point
{
       char vertex[3];
       struct Link *work;
       struct Point *next;
};
struct Link
{
       char vertex[3];
       int value;
       struct Link *next;
};
struct Table /*the workbannch of the algorithm*/
{
       int cost;
       int Known;
       char vertex[3];
       char path[3];
       struct Table *next;
};
int Dijkstra(struct Point *,struct Table *);
int PrintTable(int,struct Table *);
int PrintPath(int,struct Table *,struct Table *);
struct Table * CreateTable(int,int);
struct Point * FindSmallest(struct Table *,struct Point *);/*Find the vertex which has the smallest value reside in the table*/
int main()
{
       int i,j,num,temp,val;
       char c;
       struct Point *poinpre,*poinhead,*poin;
       struct Link *linpre,*linhead,*lin;
       struct Table *tabhead;
       poinpre=poinhead=poin=(struct Point *)malloc(sizeof(struct Point));
       poin->next=NULL;
       poin->work=NULL;
       restart:
       printf("Notice:if you wanna to input a vertex,you must use the format of number!\n");
       printf("Please input the number of points:\n");
       scanf("%d",&num);
       if(num>maxver||num<1||num%1!=0)
       {
              printf("\nNumber of points exception!");
              goto restart;
       }
       for(i=0;i       {
              printf("Please input the points next to point %d,end with 0:\n",i+1);
              poin=(struct Point *)malloc(sizeof(struct Point));
              poinpre->next=poin;
              poin->vertex[0]='v';
              poin->vertex[1]='0'+i+1;
              poin->vertex[2]='\0';
              linpre=lin=poin->work;
              linpre->next=NULL;
              for(j=0;j              {
              printf("The number of the %d th vertex linked to vertex %d:",j+1,i+1);
              scanf("%d",&temp);
              if(temp==0)
                     {
                     lin->next=NULL;
                     break;
                     }
              else
                     {
                     lin=(struct Link *)malloc(sizeof(struct Link));
                     linpre->next=lin;
                     lin->vertex[0]='v';
                     lin->vertex[1]='0'+temp;
                     lin->vertex[2]='\0';
                     printf("Please input the value betwixt %d th point towards %d th point:",i+1,temp);
                     scanf("%d",&val);
                     lin->value=val;
                     linpre=linpre->next;
                     lin->next=NULL;
                     }
              }
              poinpre=poinpre->next;
              poin->next=NULL;
       }
       printf("Please enter the vertex where Dijkstra algorithm starts:\n");
       scanf("%d",&temp);
       tabhead=CreateTable(temp,num);
       Dijkstra(poinhead,tabhead);
       PrintTable(temp,tabhead);
       return OK;
}
struct Table * CreateTable(int vertex,int total)
{
       struct Table *head,*pre,*p;
       int i;
       head=pre=p=(struct Table *)malloc(sizeof(struct Table));
       p->next=NULL;
       for(i=0;i       {
              p=(struct Table *)malloc(sizeof(struct Table));
              pre->next=p;
              if(i+1==vertex)
              {
                     p->vertex[0]='v';
                     p->vertex[1]='0'+i+1;
                     p->vertex[2]='\0';
                     p->cost=0;
                     p->Known=0;
              }
              else
              {
                     p->vertex[0]='v';
                     p->vertex[1]='0'+i+1;
                     p->vertex[2]='\0';
                     p->cost=maxium;
                     p->Known=0;
              }
              p->next=NULL;
              pre=pre->next;
       }
       return head;
}
int Dijkstra(struct Point *p1,struct Table *p2) /* Core of the programm*/
{
       int costs;
       char temp;
       struct Point *poinhead=p1,*now;
       struct Link *linna;
       struct Table *tabhead=p2,*searc,*result;
       while(1)
       {
              now=FindSmallest(tabhead,poinhead);
              if(now==NULL)
                     break;
              result=p2;
              result=result->next;
              while(result!=NULL)
              {
                     if(result->vertex[1]==now->vertex[1])
                            break;
                     else
                            result=result->next;
              }
              linna=now->work->next;
              while(linna!=NULL) /* update all the vertexs linked to the signed vertex*/
              {
                     temp=linna->vertex[1];
                     searc=tabhead->next;
                     while(searc!=NULL)
                     {
                            if(searc->vertex[1]==temp)/*find the vertex linked to the signed vertex in the table and update*/
                            {
                                   if((result->cost+linna->value)cost)
                                   {
                                   searc->cost=result->cost+linna->value;/*set the new value*/
                                   searc->path[0]='v';
                                   searc->path[1]=now->vertex[1];
                                   searc->path[2]='\0';
                                   }
                                   break;
                            }
                            else
                                   searc=searc->next;
                     }
                     linna=linna->next;
              }
       }
       return 1;
}
struct Point * FindSmallest(struct Table *head,struct Point *poinhead)
{
       struct Point *result;
       struct Table *temp;
       int min=maxium,status=0;
       head=head->next;
       poinhead=poinhead->next;
       while(head!=NULL)
       {
              if(!head->Known&&head->cost              {
                     min=head->cost;
                     result=poinhead;
                     temp=head;
                     status=1;
              }
              head=head->next;
              poinhead=poinhead->next;
       }
       if(status)
       {
              temp->Known=1;
              return result;
       }
       else
              return NULL;
}
int PrintTable(int start,struct Table *head)
{
       struct Table *begin=head;
       head=head->next;
       while(head!=NULL)
       {
              if((head->vertex[1]-'0')!=start)
                     PrintPath(start,head,begin);
              head=head->next;
       }
       return OK;
}
int PrintPath(int start,struct Table *head,struct Table *begin)
{
       struct Table *temp=begin->next,*p,*t;
       p=head;
       t=begin;
       if((p->vertex[1]-'0')!=start&&p!=NULL)
       {
              while(temp->vertex[1]!=p->path[1]&&temp!=NULL)
                     temp=temp->next;
              PrintPath(start,temp,t);
              printf("%s",p->vertex);
       }
       else
              if(p!=NULL)
              printf("\n%s",p->vertex);
       return OK;
}


本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/ctu_85/archive/2006/11/17/1393130.aspx

阅读(2011) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~