yuanyuelang
导航
C++博客
首页
新随笔
联系
聚合
管理
<
2024年12月
>
日
一
二
三
四
五
六
24
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
留言簿
给我留言
查看公开留言
查看私人留言
随笔分类
编程之美
(rss)
编程珠玑
(rss)
文章分类
计算几何学
(rss)
数据结构(1)
(rss)
数论(4)
(rss)
图论(4)
(rss)
转载(1)
(rss)
文章档案
2010年4月 (1)
2009年9月 (9)
阅读排行榜
评论排行榜
常用链接
我的随笔
我的评论
我参与的随笔
统计
随笔 - 0
文章 - 10
评论 - 5
引用 - 0
最新评论
1. re: 数论(2)-------扩展欧几里得算法
定理:gcd(a,b) = gcd(b,a mod b) (a>b 且a mod b 不为0)
--s
2. re: 数论(2)-------扩展欧几里得算法
min=y-[y/a]y错了.
--CrazyForAC
3. re: 数论(2)-------扩展欧几里得算法
评论内容较长,点击标题查看
--晓楠
4. re: 数论(2)-------扩展欧几里得算法
顶
--ding
5. re: 不相交集合数据结构[未登录]
太简陋了一点吧
--a
单源最短路径之Dijkstra算法
单源最短路径,解决的是什么问题呢?
顾名思义,单源说明从一个源出发,出发到哪里呢?不管到哪里我都要求得一个最短的路径。
比较正式的说法:
对于有向图G={V,E},带权,注意Dijkstra算法要求所有的权值非负,
假设我们的源是s,源点要到达的点集合是S,我们每次选择具有最短路径估计的顶点u(u在V-S中,并将u加入到S中,然后此时要对u所有的出边进行处理,怎么处理,我们要最短路径,所以此时要判断s经过u到达V-S中的点会不会比不经过u到达来的小,更新呵呵..
那么怎么写成代码呢?
1.我们需要二维数组graph[][]表示图,用distance[]数组来表示源点V0到其它顶点的最短路径distance[v],我们还要保存具体路径,我们用path[][]二维bool数组来表示,path[1]就表示源点到顶点V1的路径,path[1][0,n-1]数组里面的元素如果为true表示V0有经过那些顶点到达V1
2.我们还要考虑到顶点是否已经加到S中,用一个flag数组来标志顶点是否已经求的最短路径了。
还要分清是有向图还是无向图,这对于入边和出边在程序处理的时候要注意。
#define
MAXN 100
#define
INF 0xfffffff
//
注意graph里面的数据,两顶点i指向j有边,长为r,则graph[i][j]=r,其余情况graph为INF,包括i==j
void
dijkstra(
int
graph[MAXN][MAXN],
bool
path[MAXN][MAXN],
int
distance[],
int
n)
{
int
i,j,min,vertex;
bool
flag[MAXN];
for
(i
=
0
;i
<
n;i
++
)
{
//
初始化
distance[i]
=
graph[
0
][i];
flag[i]
=
false
;
for
(j
=
0
;j
<
n;j
++
) path[i][j]
=
false
;
if
(distance[i]
<
INF)
{
//
路径必定至少有v0和vi两个顶点
p[i][
0
]
=
true
;p[i][i]
=
true
;
}
}
flag[
0
]
=
true
;
distance[
0
]
=
0
;
//
注意一定要初始化distance[0]
for
(i
=
1
;i
<
n;i
++
)
{
min
=
INF;
for
(j
=
1
;j
<
n;j
++
)
if
(
!
flag[j]
&&
distance[j]
<
min)
{
//
找到最近的点
min
=
distance[j];
vertex
=
j;
}
flag[vertex]
=
true
;
for
(j
=
1
;j
<
n;j
++
)
if
(
!
flag[j]
&&
graph[vertex][j]
+
min
<
distance[j])
{
//
如果可以通过vertex更近的话,更新
distance[j]
=
graph[vertex][j]
+
min;
for
(
int
k
=
0
;k
<
n;k
++
) path[j][k]
=
path[vertex][k];
path[j][j]
=
true
;
}
}
}
请读者务必自己举个例子,运行看看,这样子才能理解好理解的根深蒂固,还有一定要自己不断的写,自己平常要锻炼,做ACM题目时最好自己再写一遍,不要太依赖模板了哈哈。。
posted on 2009-09-14 21:21
原语饿狼
阅读(614)
评论(0)
编辑
收藏
引用
所属分类:
图论
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
每对顶点间的最短路径之Floyd-Warshall算法
单源最短路径之Dijkstra算法
最小生成树之Prim算法
最小生成树之Kruskal算法
网站导航:
博客园
IT新闻
BlogJava
博问
Chat2DB
管理
Powered by:
C++博客
Copyright © 原语饿狼