| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 955 人关注过本帖
标题:求最短路径!
只看楼主 加入收藏
djx20040701
Rank: 1
等 级:新手上路
帖 子:44
专家分:0
注 册:2006-4-20
收藏
 问题点数:0 回复次数:4 
求最短路径!


程序有问题,麻烦高手修改 !


#include "stdio.h"
#include "stdlib.h"
#define N 6 // 顶点数
#define S 0 // 尚未求出最短路径
#define T 1 // 已经求出最短路径
#define M 10000

///////////////////////////////////////////////////////

void dijkstra(int cost[][N],int v,int dist[],char path[][N]); //计算v到其余各顶点的最短距离dist[],最短路径path[N][N]
int mincost(int dist[],int set[]); //在S集合中找顶点w,dist[w]是dist[]中的最小值
void strcat(char path_j[],char path_w[],int w); // 合并路径

///////////////////////////////////////////////////////函数说明
void main()
{
int cost[N][N]={
{0 ,M ,10 ,M ,30 ,100},
{M ,0 ,5 ,M ,M ,M },
{M ,M ,0 ,50 ,M ,M },
{M ,M ,M ,0, M ,10 },
{M ,M ,M ,20 ,0 ,60 },
{100,M ,M ,M ,M ,M },
};

int dist[N]; char path[N][N]; /* 路径字符串 */
dijkstra(cost,0,dist,path); /* 起点为顶点0 */
}

//计算v到其余各顶点的最短距离dist[],最短路径path[N][N]
void dijkstra(int cost[][N],int v,int dist[],char path[][N])
{ int set[N], i,j,nearest_v;
for(i=0; i<N; i++)
{ dist[i]=cost[v][i]; set[i]=S;
path[i][0]='\0'; /* 路径字符串初始化为空 */
}
for(set[v]=T,i=1; i<N; i++)
{
nearest_v=mincost(dist,set);
for(set[nearest_v]=T,j=0; j<N; j++)
if(set[j]==S && dist[nearest_v]+cost[nearest_v][j]<dist[j])
{
dist[j]=dist[nearest_v]+cost[nearest_v][j];
strcat(path[j],path[nearest_v],nearest_v); //合并路径
}
}
}

//在S集合中找顶点w,dist[w]是dist[]中的最小值/
int mincost(int dist[],int set[])
{
int i,min,w;
for(min=M,i=0; i<N; i++) /* N为顶点数 */
if(set[i]==S && dist[i]<min) { min=dist[i]; w=i; }
return(w);
}

// 合并路径
void strcat(char path_j[],char path_w[],int w)
{ int i;
for(i=0; path_w[i]!='\0'; i++) path_j[i]=path_w[i];
path_j[i++]=w+'0'; path_j[i]='\0';
}

搜索更多相关主题的帖子: 路径 
2006-05-23 09:05
–★–
Rank: 3Rank: 3
等 级:新手上路
威 望:6
帖 子:1512
专家分:0
注 册:2006-5-1
收藏
得分:0 
dijkstra算法实现问题可能放在"数据结构"吧合适些

落霞与孤鹜齐飞,秋水共长天一色! 心有多大,路有多宽。三教九流,鸡鸣狗盗。兼收并蓄,海纳百川。
2006-05-23 10:26
独角龙
Rank: 1
等 级:新手上路
帖 子:221
专家分:0
注 册:2006-5-5
收藏
得分:0 
不会!

奋斗改变一切!!
2006-05-23 18:40
cordier
Rank: 2
等 级:论坛游民
威 望:1
帖 子:449
专家分:14
注 册:2006-2-9
收藏
得分:0 

用Floyd好像会更好一些


2006-05-24 08:32
快速回复:求最短路径!
数据加载中...
 
   



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

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