原来是这样的， 每次从候选集合dist选取一个加入set中， 然后调整候选集， 使其满足， d[u] 为起点经过set里面的点到达u的最短路径。
这是我理解写的从1->n的dijkstra程序:
struct
COSTDATA
{
int
q;
int
visit;
}
;
int
dijkstra(
int
n)
{
int
i, j, u, min;
COSTDATA dist[MAXN];
int
set
[MAXN];
int
setNum;
set
[
1
]
=
1
; dist[
1
].visit
=
-
1
; dist[
1
].q
=
0
;
setNum
=
1
;
for
(i
=
2
; i
<=
n; i
++
)
{
dist[i].q
=
g[
1
][i];
dist[i].visit
=
0
;
}
while
(setNum
<
n)
{
min
=
MAXNUM;
for
(i
=
1
; i
<=
n; i
++
)
{
if
(min
>
dist[i].q
&&
dist[i].visit
!=
-
1
)
{
u
=
i;
min
=
dist[i].q;
}
}
dist[u].visit
=
-
1
;
set
[
++
setNum]
=
u;
for
(i
=
1
; i
<=
n; i
++
)
{
if
(dist[i].visit
!=
-
1
&&
dist[i].q
>
dist[u].q
+
g[u][i])
{
dist[i].q
=
dist[u].q
+
g[u][i];
}
}
}
return
dist[n].q;
}
我再根据wy的代码，再优化了一下， 以下是任意两点的最短路径程序：
/**/
/*
* beg : 起点;
* end : 终点;
* n : 顶点个数;
* g : 邻接矩阵, 为全局变量, 下标(1, 1)起;
*/
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
;
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];
}
}
if
(u
==
end)
break
;
}
return
dist[end];
}
posted on 2006-08-09 14:51
豪 阅读(1532)
评论(1) 编辑 收藏 引用 所属分类:
算法&ACM