| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 6753 人关注过本帖, 1 人收藏
标题:利用Dijkstra算法实现最短路径搜索
只看楼主 加入收藏
牛虻
Rank: 1
等 级:新手上路
威 望:1
帖 子:472
专家分:0
注 册:2004-10-1
收藏(1)
 问题点数:0 回复次数:19 
利用Dijkstra算法实现最短路径搜索

#include<stdio.h>

#define INFINITY 10000 #define MaxVertexNum 100 #define FALSE 0 #define TRUE 1

typedef char Vertex_Type; typedef char Path_Matrix; typedef int Short_Path_Table; typedef int Edge_Type;

typedef struct{ Vertex_Type vexs[MaxVertexNum]; Edge_Type edges[MaxVertexNum][MaxVertexNum]; int n,e;}MGraph;

void ShortestPath(MGraph *G,int v0,Path_Matrix P[],Short_Path_Table D[]) {int v,i,min,pre,w,final[MaxVertexNum]; for(v=0;v<G->n;++v) {final[v]=FALSE;D[v]=G->edges[v0][v]; P[v0]=-1; if(D[v]<INFINITY&&v!=v0)P[v]=v0; if(D[v]==INFINITY) P[v]=-2;} D[v0]=0;final[v0]=TRUE; for(i=1;i<G->n;++i) {min=INFINITY; for(w=0;w<G->n;++w) if(!final[w]) if(D[w]<min){v=w;min=D[w];} final[v]=TRUE; for(w=0;w<G->n;++w) if(!final[w]&&(min+G->edges[v][w])<D[w]) {D[w]=min+G->edges[v][w]; P[w]=v;} } for(i=1;i<G->n;i++) {if(P[i]==-2) printf("max %d\n",i); else {printf("%d v%i",D[i],i); pre=P[i]; while(pre>0) {printf("<-%s",G->vexs[pre]);pre=P[pre];} printf("<-v0\n");} }}

main() {MGraph *G; Path_Matrix P[MaxVertexNum]; Short_Path_Table D[MaxVertexNum]; int v0=0,i,j,k,w; clrscr(); G=(MGraph *)malloc(sizeof(MGraph)); printf("Input totals of Vertexs and Edges(e.g:Vertex_Totals,Edge_Totals):\n");/*对图的初始化,给图的顶点数和边数赋值*/ scanf("%d,%d",&G->n,&G->e); printf("Input information for Vertexs(e.g:Vertex_SN<CR>):\n");/*给图的每个顶点输入一个序列号*/ for(i=0;i<G->n;i++) scanf("%s",G->vexs[i]); for(i=0;i<G->n;i++) for(j=0;j<G->n;j++) G->edges[i][j]=INFINITY;/*设定一个最大值给每条边,让每个顶点初始化的时候相当于权值无穷大即互不相连*/ printf("Input every edge together two Vertexs' SN(e.g:i,j):\n"); for(k=0;k<G->e;k++) /*输入要进行赋值的边所确定的两个顶点*/ {scanf("%d,%d",&i,&j); printf("weight of the edge<v%d,v%d>:",i,j);/*给固定的边赋值*/ scanf("%d",&G->edges[i][j]);} ShortestPath(G,v0,P,D);/*Dijkstra算法的注释书上有,我就不赘述了*/ getch();} 

其实这个程序并没有什么难点,算法给定,剩下的都是参数传入的匹配。

[此贴子已经被作者于2005-5-14 0:13:37编辑过]

搜索更多相关主题的帖子: Dijkstra 算法 int 路径 typedef 
2005-05-14 00:00
牛虻
Rank: 1
等 级:新手上路
威 望:1
帖 子:472
专家分:0
注 册:2004-10-1
收藏
得分:0 

运行结果如下:

图片附件: 游客没有浏览图片的权限,请 登录注册

图片附件: 游客没有浏览图片的权限,请 登录注册

[此贴子已经被作者于2005-5-14 0:11:46编辑过]



qI3lAgzS.jpg (25.69 KB)
图片附件: 游客没有浏览图片的权限,请 登录注册

土冒
2005-05-14 00:10
牛虻
Rank: 1
等 级:新手上路
威 望:1
帖 子:472
专家分:0
注 册:2004-10-1
收藏
得分:0 
还有一种可以用Floyd算法做的,哪位再做一下传上来一下,这个求最短路径的问题就全了

土冒
2005-05-14 00:15
ぁ小甜瓜ぁ
Rank: 1
等 级:新手上路
帖 子:8
专家分:0
注 册:2005-5-20
收藏
得分:0 
没人理你
呵呵
我也会
2005-05-20 07:45
ぁ小甜瓜ぁ
Rank: 1
等 级:新手上路
帖 子:8
专家分:0
注 册:2005-5-20
收藏
得分:0 
偶不会做,看你做的还可以,请留下QQ,邮箱地址。偶想和你做朋友!
共同交流。
2005-05-22 19:35
tary
Rank: 1
等 级:新手上路
帖 子:780
专家分:0
注 册:2004-10-5
收藏
得分:0 

我做的校园导游程序,, 是用Floyd算法求最短路径的, 不想改了... 就这样了.. #include<string.h> #include<iostream> #define MaxVertexNum 100 #define INFITY 200 using namespace std; typedef int EdgeType; typedef char VertexType; typedef int pathMatrix; typedef int distancMatrix; typedef struct{ VertexType vexs[MaxVertexNum]; EdgeType edges[MaxVertexNum][MaxVertexNum]; int n,e; }MGraph; typedef struct{ char data; char name[20]; int number; char introduce[60]; } vertex;

void shortest_path(MGraph *G,pathMatrix p[MaxVertexNum][MaxVertexNum],distancMatrix D[MaxVertexNum][MaxVertexNum]) { int v,w,u,i,j; for(v=0;v<G->n;++v) for(w=0;w<G->n;++w) {D[v][w]=G->edges[v][w]; /* 把边权值的邻接矩阵赋给D数组*/ if(D[v][w]<INFITY&&D[v][w]!=0) p[v][w]=v; else if(v!=w) p[v][w]=-2; if(v==w) p[v][w]=-1; /*初始化P数组*/ } for(u=0;u<G->n;++u) for(v=0;v<G->n;++v) for(w=0;w<G->n;++w) if(D[v][u]+D[u][w]<D[v][w]) {D[v][w]=D[v][u]+D[u][w]; /*当v w之间有一点u使用vu的长度加上uw的长度小于 vw的长度, 把相应的P改变,同时改变D数组*/ p[v][w]=u; } cout<<"please input you choice between i and j:\n"; cin>>i; cin>>j; if(i>=6||j>=6) cout<<"对不起.您输入的景点不存在, 请重新输入.\n"; /*本题我只定义了六个结点*/ else {cout<<"you choice is between "<<G->vexs[i]<<"---and---"<<G->vexs[j]; cout<<endl; if(p[i][j]>=0) {w=j; /*输出部分*/ cout<<"您所选择的两景点间的长度为:"; cout<<D[i][j]; cout<<endl; cout<<"您所选择的景点的代号为:"; cout<<G->vexs[j];

cout<<"<--"; while(p[i][w]!=i) { cout<<G->vexs[p[i][w]]; w=p[i][w]; cout<<"<--"; } cout<<G->vexs[i]<<endl; } else cout<<"sorry,you choice is not exist.plese try again.\n"; } }

void start() { cout<<"********************************************\n"; cout<<" 校园导游图 \n"; cout<<" 福建工程学院 j0303 41号 周谅友\n"; cout<<"*********************************************\n"; cout<<"请选择操作:\n"; cout<<"0.退出\n"; cout<<"1.任意两个景点间的最短路径\n"; cout<<"2.各个景点的讯息\n"; cout<<"3.用户手册\n"; }

void Readme() { cout<<"**********用户手册***************************\n"; cout<<"****查询任意两个景点间的最短路径****\n"; cout<<"请注意:共有六个景点可供选择,数字:0-5\n"; cout<<"输入您要查询的两个景点的数字, 例如0回车5\n"; cout<<"**********各个景点的讯息*************\n"; cout<<"1.请输入您要查询的景点的编号\n"; cout<<"2.例如.. 001 002--006\n"; cout<<"**********感谢你的使用!^_^****************\n"; cout<<endl; }

main() {MGraph *G; int i,j,k,w,m,number_2,l; vertex t[2]; G=(MGraph *)malloc(sizeof(MGraph)); G->n=6; /*初始化关于G图的各个讯息*/ G->e=8; /*初始化边数跟顶点数*/ G->vexs[0]='a';G->vexs[1]='b'; G->vexs[2]='c'; G->vexs[3]='d'; G->vexs[4]='e'; G->vexs[5]='f'; /* 建立顶点讯息*/

for(i=0;i<G->n;i++) for(j=0;j<G->n;j++) {if(i==j) G->edges[i][j]=0; else G->edges[i][j]=INFITY; }

G->edges[0][2]=10;G->edges[0][4]=30;G->edges[0][5]=100; G->edges[1][2]=5; G->edges[2][3]=50;G->edges[3][5]=10; G->edges[4][3]=20;G->edges[4][5]=60;/*建立图中所有的连接点跟权值*/

pathMatrix p[MaxVertexNum][MaxVertexNum]; distancMatrix D[MaxVertexNum][MaxVertexNum]; l=-1;

t[0].data='a'; strcpy(t[0].name,"class");t[0].number=001; strcpy(t[0].introduce,"all of the lesson are held at here!!"); t[1].data='b'; strcpy(t[1].name,"lab");t[1].number=002; strcpy(t[1].introduce,"we do very experience at here!!"); t[2].data='c'; strcpy(t[2].name,"garden");t[2].number=003; strcpy(t[2].introduce,"we can wander after dinner at here ohch!!"); t[3].data='d'; strcpy(t[3].name,"playground");t[3].number=004; strcpy(t[3].introduce,"it is a field to play togerther!!"); t[4].data='e'; strcpy(t[4].name,"privacy");t[4].number=005; strcpy(t[4].introduce,"it is a good place for lover!!"); t[5].data='f'; strcpy(t[5].name,"lake");t[5].number=006; strcpy(t[5].introduce,"you can see lots of fishes is siwiming there!"); /*建立结点的各个讯息*/

start();

while(l!=0) { cin>>l; switch(l) { case 0: return; case 1: cout<<"您选择的是得知任意两个景点间的最短路径\n"; shortest_path(G,p,D);

l=-1; start(); break;

case 2:

cout<<"您选择的是各个景点的讯息"<<endl; cout<<"please input your choice:\n"; cin>>number_2; if(number_2>=007) cout<<"对不起.您输入的景点不存在, 请重新输入.\n"; else{ for(i=0;i<6;i++) { if(t[i].number==number_2) {k=i; cout<<"the data is:"<<t[k].data<<endl; cout<<"the name is:"<<t[k].name<<endl; cout<<"the introduction:"<<t[k].introduce<<endl; } } } l=-1; start(); break;

case 3: cout<<"您选择的是用户手册\n"; cout<<endl; Readme(); l=-1; start(); break;

default: cout<<"输入有误!请重新选择操作!\n"; start();

} }

}


┌→¨ ≮我可以学会对你很冷落≯¨←┐ │  <却学不╓══╦══╖会将爱> │ │¨←┐ ╭╩╮哭‖哭╭╩╮ ┌→¨│ └──┘收 ╲╱ ◇‖◇ ╲╱回└──┘
2005-05-25 16:54
piaofeng
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2005-5-29
收藏
得分:0 
heheh
xiexie   

不只是诱人——不只是神秘——不只是聪明
2005-05-31 11:00
120329
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2005-7-1
收藏
得分:0 
校园导游程序Floyd算法求最短路径
--------------------------------------------------
错误  temp.c 2: 不能打开包文件 'iostream'
错误  temp.c 5: 说明语法错误
错误  temp.c 39: 未定义的符号'cout' 在函数        
错误  temp.c 39: 非法指针运算 在函数        
错误  temp.c 40: 未定义的符号'cin' 在函数        
警告?  temp.c 40: 无效操作代码 在函数        
警告?  temp.c 40: 可能在'i'定义以前使用了它 在函数        
警告?  temp.c 41: 无效操作代码 在函数        
警告?  temp.c 41: 可能在'j'定义以前使用了它 在函数        
警告?  temp.c 42: 可能在'i'定义以前使用了它 在函数        
警告?  temp.c 42: 可能在'j'定义以前使用了它 在函数        
错误  temp.c 42: 非法指针运算 在函数        
错误  temp.c 43: 非法指针运算 在函数        
错误  temp.c 43: 未定义的符号'endl' 在函数        
警告?  temp.c 43: 无效操作代码 在函数        
警告?  temp.c 44: 可能在'i'定义以前使用了它 在函数        
警告?  temp.c 44: 可能在'j'定义以前使用了它 在函数        
警告?  temp.c 45: 可能在'j'定义以前使用了它 在函数        
错误  temp.c 46: 非法指针运算 在函数        
警告?  temp.c 46: 无效操作代码 在函数        
警告?  temp.c 46: 可能在'i'定义以前使用了它 在函数        
警告?  temp.c 46: 可能在'j'定义以前使用了它 在函数        
警告?  temp.c 46: 无效操作代码 在函数        
错误  temp.c 46: 非法指针运算 在函数        
警告?  temp.c 46: 无效操作代码 在函数        
警告?  temp.c 46: 可能在'j'定义以前使用了它 在函数        
错误  temp.c 48: 非法指针运算 在函数        
警告?  temp.c 49: 可能在'i'定义以前使用了它 在函数        
警告?  temp.c 49: 可能在'i'定义以前使用了它 在函数        
警告?  temp.c 51: 无效操作代码 在函数        
警告?  temp.c 51: 可能在'i'定义以前使用了它 在函数        
警告?  temp.c 52: 可能在'i'定义以前使用了它 在函数        
错误  temp.c 53: 非法指针运算 在函数        
警告?  temp.c 56: 无效操作代码 在函数        
警告?  temp.c 56: 可能在'i'定义以前使用了它 在函数        
错误  temp.c 59: 非法指针运算 在函数        
错误  temp.c 65: 未定义的符号'cout' 在函数        
错误  temp.c 65: 非法指针运算 在函数        
错误  temp.c 66: 非法指针运算 在函数        
错误  temp.c 67: 非法指针运算 在函数        
错误  temp.c 68: 非法指针运算 在函数        
错误  temp.c 69: 非法指针运算 在函数        
错误  temp.c 70: 非法指针运算 在函数        
错误  temp.c 71: 非法指针运算 在函数        
错误  temp.c 72: 非法指针运算 在函数        
错误  temp.c 73: 非法指针运算 在函数        
错误  temp.c 79: 未定义的符号'cout' 在函数        
错误  temp.c 79: 非法指针运算 在函数        
错误  temp.c 79: 太多的错或警告信息 在函数        


水能帮我改下啊
2005-07-01 17:31
tary
Rank: 1
等 级:新手上路
帖 子:780
专家分:0
注 册:2004-10-5
收藏
得分:0 
晕,, 我那个程序是在C++里面编译的,,
你要在C里面编译的话, 输入输出函数还有头文件改下啊。。。!!
当然了,C++的语法要求会比C简单些,,所以,有些地方还是要改下。。

┌→¨ ≮我可以学会对你很冷落≯¨←┐ │  <却学不╓══╦══╖会将爱> │ │¨←┐ ╭╩╮哭‖哭╭╩╮ ┌→¨│ └──┘收 ╲╱ ◇‖◇ ╲╱回└──┘
2005-07-01 17:56
120329
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2005-7-1
收藏
得分:0 

#include <string.h> #include <iostream.h> #define MaxVertexNum 100 #define INFITY 200 #include <vector> 校园导游程序Floyd算法求最短路径.C c:\program files\microsoft visual studio\vc98\include\eh.h(32) : fatal error C1189: #error : "eh.h is only for C++!" Error executing cl.exe.

flopy2.exe - 1 error(s), 0 warning(s) 。。。。我快晕了 我改了头文件啊~可是在VC6。0里还是

2005-07-01 21:01
快速回复:利用Dijkstra算法实现最短路径搜索
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.020684 second(s), 10 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved