单源最短路径Dijkstra - &豪

My friends

搜索

积分与排名

积分 - 214755

排名 - 116

最新评论

1. re: 使用JS呼叫另一PHP程式后直接返回数值而不必翻新页面（转）
123456
--Jaxk
2. re: qsort函数应用大全(转)
对头@莫名

博主谢谢分享，学习了！
--呵呵哒
3. re: 三次样条插值
评论内容较长,点击标题查看
--mrsong123mtr
4. re: 三次样条插值
请楼主加解释啊，表示好难懂
--mrsong123mtr
5. re: 三次样条插值
楼主写的是自然边界条件的样条插值。。。可以参考《计算方法》一书
--juy

阅读排行榜

评论排行榜

单源最短路径Dijkstra

* beg : 起点;

* end : 终点;

* n : 顶点个数;

* g : 邻接矩阵, 为全局变量, 下标(1, 1)起;

int pre[MAXN];

int dijkstra( int beg, int end, int n)

{

int i, j, u, min;

int * dist = new int [n + 1 ];

int * visit = new int [n + 1 ];

for (i = 1 ; i <= n; i ++ ) {

dist[i] = MAXNUM;

visit[i] = false ;

}

dist[beg] = 0 ; pre[beg] = - 1 ;

for (i = 0 ; i < n; i ++ ) {

min = MAXNUM;

for (j = 1 ; j <= n; j ++ ) {

if (min > dist[j] && ! visit[j]) {

u = j;

min = dist[j];

}

if (min == MAXNUM) break ;

visit[u] = true ;

for (j = 1 ; j <= n; j ++ ) {

if ( ! visit[j] && dist[j] > dist[u] + g[u][j]) {

dist[j] = dist[u] + g[u][j];

pre[j] = u;

}

if (u == end) break ;

}

return dist[end];

}

posted on 2006-08-09 14:56 豪阅读(323) 评论(0) 编辑收藏引用所属分类: 数据结构与算法

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！

相关文章: 红黑树（数据结构大作业扩展版） pku3268 dij+heap 线段树类 LIS O(nlogn) 凸包... MinHeap 树状数组 [转贴] 快速计算某个日期是星期几的经验公式拓扑排序合并排序

网站导航: 博客园 IT新闻 BlogJava 博问 Chat2DB 管理

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜