原來是這樣的， 每次從候選集合dist選取一個(gè)加入set中， 然后調(diào)整候選集， 使其滿足， d[u]?為起點(diǎn)經(jīng)過set里面的點(diǎn)到達(dá)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;
}
?我再根據(jù)wy的代碼，再優(yōu)化了一下， 以下是任意兩點(diǎn)的最短路徑程序：
/**/
/*
?*????beg?:?起點(diǎn);
?*??end?:?終點(diǎn);
?*??n?:?頂點(diǎn)個(gè)數(shù);
?*??g?:?鄰接矩陣,?為全局變量,?下標(biāo)(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
豪 閱讀(1570)
評論(1) 編輯 收藏 引用 所屬分類:
算法&ACM