焦磷酸钾的食品作用:Dijkstra算法的完整实现版本之算法的源代码

来源：百度文库 编辑：中财网 时间：2024/05/06 00:53:52
 Dijkstra算法的完整实现版本之算法的源代码 样例图:输入格式:输出格式:输入时，将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 1struct 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;inext=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;jnext=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;inext=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->costcost;                     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;}更多内容:Prim算法代码分析
http://blog.csdn.net/ctu_85/archive/2006/12/16/1445156.aspx浙江大学ACM试题解答(四月)
http://blog.csdn.net/ctu_85/archive/2007/04/24/1576831.aspx
浙江大学ACM试题解答(三月)
http://blog.csdn.net/ctu_85/archive/2007/03/20/1535556.aspx
麻省理工算法导论翻译
http://blog.csdn.net/ctu_85/archive/2007/06/08/1643179.aspx
华容道游戏与算法
http://blog.csdn.net/ctu_85/archive/2007/05/15/1610722.aspx
中国象棋对战程序C语言源代码
http://blog.csdn.net/ctu_85/archive/2007/05/04/1596351.aspx文件加密解密源代码分析http://blog.csdn.net/ctu_85/archive/2006/12/23/1455515.aspx
Kruskal算法代码分析
http://blog.csdn.net/ctu_85/archive/2006/12/16/1445147.aspx荷兰国旗算法分析http://blog.csdn.net/ctu_85/archive/2007/01/03/1472994.aspx
银行家算法代码分析
http://blog.csdn.net/ctu_85/archive/2006/09/09/1198551.aspx
更多试题解答:
两种计算Ack(m,n)的非递归算法
http://blog.csdn.net/ctu_85/archive/2006/11/29/1419396.aspx
上海交通大学1999年
http://blog.csdn.net/ctu_85/archive/2006/11/09/1376289.aspx
东北大学2001年
http://blog.csdn.net/ctu_85/archive/2006/11/09/1376287.aspx
清华大学1994年
http://blog.csdn.net/ctu_85/archive/2006/10/24/1349754.aspx
中国科学院2002年
http://blog.csdn.net/ctu_85/archive/2006/10/24/1349704.aspx
浙江大学计算机复试解答1
http://blog.csdn.net/ctu_85/archive/2006/10/15/1334936.aspx
浙江大学计算机复试解答2
http://blog.csdn.net/ctu_85/archive/2006/10/16/1336101.aspx
浙江大学计算机复试解答3
http://blog.csdn.net/ctu_85/archive/2006/11/02/1363159.aspx
软件可行性报告
http://blog.csdn.net/ctu_85/archive/2006/06/06/775894.aspx
软件需求分析报告
http://blog.csdn.net/ctu_85/archive/2006/06/06/775892.aspx


Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1393130

怎么编程实现求图最短路的Dijkstra算法 dijkstra算法的改进程序 dijkstra算法的改进程序 关于Dijkstra 算法的一个问题 dijkstra算法是什么？ Dijkstra算法算最短路径 dijkstra算法解决“狼羊菜”问题 求C++的dijkstra算法或者floyd算法的参考源代码 求助Dijkstra迪杰的VC++算法 毕业设计 急~~~跪求 所有用递归算法的能不能都用非递归算法实现? des加密解密算法的完整程序 用C++实现二叉排序树的各种算法 平衡二叉树的各种算法实现 crc算法在单片机上的实现 哈夫曼编码算法实现的源程序 crc算法在单片机上的实现 哈夫曼编码算法实现的VB源程序 m树索引算法的java实现 请问hash查询算法的c实现 用JAVA实现的Apriori算法 LCS算法是怎么实现的？ 一个递归算法的实现问题 求助：点灯游戏算法的实现 求助：点灯游戏算法的实现