Whier
专注游戏开发,计算机图形图像
posts - 1, comments - 0, trackbacks - 0, articles - 0
导航
C++博客
首页
新随笔
联系
聚合
管理
<
2010年10月
>
日
一
二
三
四
五
六
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
5
6
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
给我留言
查看公开留言
查看私人留言
随笔分类
c&c++程序设计(1)
socket&TCP/IP
wince嵌入式开发
windows核心编程
游戏开发
随笔档案
2010年10月 (1)
搜索
最新评论
Dijkstra Algorithm
Posted on 2010-10-30 12:21
whier
阅读(89)
评论(0)
编辑
收藏
引用
所属分类:
c&c++程序设计
算法描述参考:
http://www.cnblogs.com/gzydn/archive/2009/07/09/1520019.html
//
this program shows Dijkstra Algorithm
#include
<
stdio.h
>
#include
<
stdlib.h
>
int
main(
int
argc,
char
**
argv)
{
int
dis_metrix[
5
][
5
];
bool
is_in_s[
5
]
=
{
false
}
;
int
s[
5
];
int
dist[
5
]
=
{
0
}
;
//
init dis_metrix
for
(
int
m
=
0
; m
!=
5
;
++
m)
for
(
int
n
=
0
; n
!=
5
;
++
n)
scanf(
"
%d
"
,
&
dis_metrix[m][n]);
//
init dist
for
(
int
m
=
0
; m
!=
5
;
++
m)
dist[m]
=
dis_metrix[
0
][m];
is_in_s[
0
]
=
true
;
s[
0
]
=
0
;
dist[
0
]
=
0
;
//
begin Dijkstra Algorithm
int
i, j, k;
int
t
=
1
;
int
max;
for
(k
=
1
; k
!=
5
;
++
k)
{
//
find the shortest path out of s
max
=
1000
;
for
(i
=
0
; i
!=
5
;
++
i)
{
if
(is_in_s[i]
==
false
&&
max
>
dist[i])
{
max
=
dist[i];
t
=
i;
}
}
is_in_s[t]
=
true
;
s[k]
=
t;
//
update shortest path
for
(j
=
0
; j
!=
5
;
++
j)
{
if
(is_in_s[j]
==
false
&&
dist[j]
>
(dist[t]
+
dis_metrix[t][j]))
{
dist[j]
=
dist[t]
+
dis_metrix[t][j];
}
}
}
}
只有注册用户
登录
后才能发表评论。
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © whier