《數(shù)據(jù)結(jié)構(gòu)》第8章 圖 P222
例8.8 ?利用狄克斯特拉算法求最小生成樹
首先說幾個(gè)概念：
1、在無向圖G中，若從訂單v i 到頂點(diǎn)v j 有路徑，則稱v i 和v j 是連通的。
2、一個(gè)連通圖的生成樹是一個(gè)極小連通子圖，它含有圖中全部頂點(diǎn)，但只有構(gòu)成一顆樹的(n-1)條邊。圖的所有生成樹中具有邊上的權(quán)值之和最小的樹稱為圖的最小生成樹。
3、在一個(gè)無權(quán)的圖中，若從一頂點(diǎn)到另一頂點(diǎn)存在著一條路徑，稱該路徑上所有經(jīng)過的邊的數(shù)目為該路徑長度，它等于該路徑上的頂點(diǎn)數(shù)減1。
? ? 把路徑長度最短的那條路徑叫做最短路徑。
而狄克斯特拉算法就是求在一個(gè)圖中，從指定頂點(diǎn)到其他頂點(diǎn)的最短路徑。
書中源代碼：
#include <stdio.h>
#define
MaxSize 100
#define
INF 32767
//
INF表示∞
#define
MAXV 100
//
最大頂點(diǎn)個(gè)數(shù)
typedef
int
InfoType;
typedef
struct
{
int
no;
//
頂點(diǎn)編號(hào)
InfoType info;
//
頂點(diǎn)其他信息
} VertexType;
//
頂點(diǎn)類型
typedef
struct
//
圖的定義
{
int
edges[MAXV][MAXV];
//
鄰接矩陣
int
n,e;
//
頂點(diǎn)數(shù),弧數(shù)
VertexType vexs[MAXV];
//
存放頂點(diǎn)信息
} MGraph;
//
圖的鄰接矩陣類型
void
Ppath(
int
path[],
int
i,
int
v)
//
前向遞歸查找路徑上的頂點(diǎn)
{
int
k;
k=path[i];
if
(k==v)
return
;
//
找到了起點(diǎn)則返回
Ppath(path,k,v);
//
找頂點(diǎn)k的前一個(gè)頂點(diǎn)
printf(
"
%d,
"
,k);
//
輸出頂點(diǎn)k
}
void
Dispath(
int
dist[],
int
path[],
int
s[],
int
n,
int
v)
{
int
i;
for
(i=
0
;i<n;i++)
if
(s[i]==
1
)
{
printf(
"
從%d到%d的最短路徑長度為:%d\t路徑為:
"
,v,i,dist[i]);
printf(
"
%d,
"
,v);
//
輸出路徑上的起點(diǎn)
Ppath(path,i,v);
//
輸出路徑上的中間點(diǎn)
printf(
"
%d\n
"
,i);
//
輸出路徑上的終點(diǎn)
}
else
printf(
"
從%d到%d不存在路徑\n
"
,v,i);
}
void
Dijkstra(MGraph g,
int
v) //狄克斯特拉算法
{
int
dist[MAXV],path[MAXV];
int
s[MAXV];
int
mindis,i,j,u;
for
(i=
0
;i<g.n;i++)
{
dist[i]=g.edges[v][i];
//
距離初始化
s[i]=
0
;
//
s[]置空
if
(g.edges[v][i]<INF)
//
路徑初始化
path[i]=v;
else
path[i]=-
1
;
}
s[v]=
1
;path[v]=
0
;
//
源點(diǎn)編號(hào)v放入s中
for
(i=
0
;i<g.n;i++)
//
循環(huán)直到所有頂點(diǎn)的最短路徑都求出
{
mindis=INF;
//
mindis置最小長度初值
for
(j=
0
;j<g.n;j++)
//
選取不在s中且具有最小距離的頂點(diǎn)u
if
(s[j]==
0
&& dist[j]<mindis)
{
u=j;
mindis=dist[j];
}
s[u]=
1
;
//
頂點(diǎn)u加入s中
for
(j=
0
;j<g.n;j++)
//
修改不在s中的頂點(diǎn)的距離
if
(s[j]==
0
)
if
(g.edges[u][j]<INF && dist[u]+g.edges[u][j]<dist[j])
{
dist[j]=dist[u]+g.edges[u][j];
path[j]=u;
}
}
Dispath(dist,path,s,g.n,v);
//
輸出最短路徑
}
void
main()
{
int
i,j;
MGraph g;
g.n=
7
;g.e=
12
;
int
a[
7
][MAXV]={
{
0
,
4
,
6
,
6
,INF,INF,INF},
{INF,
0
,
1
,INF,
7
,INF,INF},
{INF,INF,
0
,INF,
6
,
4
,INF},
{INF,INF,
2
,
0
,INF,
5
,INF},
{INF,INF,INF,INF,
0
,INF,
6
},
{INF,INF,INF,INF,
1
,
0
,
8
},
{INF,INF,INF,INF,INF,INF,
0
}};
for
(i=
0
;i<g.n;i++)
//
建立圖9.16所示的圖的鄰接矩陣
for
(j=
0
;j<g.n;j++)
g.edges[i][j]=a[i][j];
printf(
"
最短路徑
:\n
"
);
Dijkstra(g,
0
);
printf(
"
\n
"
);
}
書上說：
解 利用狄克斯特拉算法可以求出從指定頂點(diǎn)（源點(diǎn)）到其他頂點(diǎn)的最短路徑，而最小生成樹是以源點(diǎn)為根，其路徑權(quán)值之和最小的生成樹，因此，由源點(diǎn)到所有其他頂點(diǎn)的最短路徑上的不重復(fù)出
現(xiàn)的邊構(gòu)成了最小的生成樹的所有邊。
具體代碼：
#include <stdio.h>
#define
MaxSize 100
#define
INF 32767
//
INF表示∞
#define
MAXV 100
//
最大頂點(diǎn)個(gè)數(shù)
typedef
int
InfoType;
typedef
struct
{
int
no;
//
頂點(diǎn)編號(hào)
InfoType info;
//
頂點(diǎn)其他信息
} VertexType;
//
頂點(diǎn)類型
typedef
struct
//
圖的定義
{
int
edges[MAXV][MAXV];
//
鄰接矩陣
int
n,e;
//
頂點(diǎn)數(shù),弧數(shù)
VertexType vexs[MAXV];
//
存放頂點(diǎn)信息
} MGraph;
//
圖的鄰接矩陣類型
void
DisMinTree(
int
path[],
int
s[],
int
n,
int
v)
//
由path求最小的生成樹
{
int
i,pre,j,k;
int
edges[MAXV][
2
],edgenum=
0
;
//
edges數(shù)組用于存放最小生成樹的所有邊,
//
edges[i][0]存放第i條邊的起點(diǎn),edges[i][1]存放第i條邊的終點(diǎn)
printf(
"
最小生成樹的所有邊:\n\t
"
);
for
(i=
0
;i<n;i++)
if
(s[i]==
1
&& i!=v)
{
j=i;
pre=path[i];
do
//
搜索最短路徑生成最小生成樹的所有邊
{
if
(edgenum==
0
)
//
將(pre,j)邊加入到edges中
{ edges[edgenum][
0
]=pre;
edges[edgenum][
1
]=j;
edgenum++;
}
else
{
k=
0
;
while
(k<edgenum&&(edges[k][
0
]!=pre||edges[k][
1
]!=j))
k++;
if
(k>=edgenum)
//
(pre,j)邊未在edges中時(shí)加入
{
edges[edgenum][
0
]=pre;
edges[edgenum][
1
]=j;
edgenum++;
}
}
j=pre;
pre=path[pre];
}
while
(pre!=v);
}
for
(k=
0
;k<edgenum;k++)
printf(
"
(%d,%d)
"
,edges[k][
0
],edges[k][
1
]);
printf(
"
\n
"
);
}
void
Dijkstra(MGraph g,
int
v)
{
int
dist[MAXV],path[MAXV];
int
s[MAXV];
int
mindis,i,j,u;
for
(i=
0
;i<g.n;i++)
{
dist[i]=g.edges[v][i];
//
距離初始化
s[i]=
0
;
//
s[]置空
if
(g.edges[v][i]<INF)
//
路徑初始化
path[i]=v;
else
path[i]=-
1
;
}
s[v]=
1
;path[v]=
0
;
//
源點(diǎn)編號(hào)v放入s中
for
(i=
0
;i<g.n;i++)
//
循環(huán)直到所有頂點(diǎn)的最短路徑都求出
{
mindis=INF;
//
mindis置最小長度初值
for
(j=
0
;j<g.n;j++)
//
選取不在s中且具有最小距離的頂點(diǎn)u
if
(s[j]==
0
&& dist[j]<mindis)
{
u=j;
mindis=dist[j];
}
s[u]=
1
;
//
頂點(diǎn)u加入s中
for
(j=
0
;j<g.n;j++)
//
修改不在s中的頂點(diǎn)的距離
if
(s[j]==
0
)
if
(g.edges[u][j]<INF && dist[u]+g.edges[u][j]<dist[j])
{
dist[j]=dist[u]+g.edges[u][j];
path[j]=u;
}
}
DisMinTree(path,s,g.n,v);
//
輸出最小生成樹
}
void
main()
{
int
i,j;
MGraph g;
g.n=
7
;g.e=
12
;
int
a[
7
][MAXV]={
{
0
,
4
,
6
,
6
,INF,INF,INF},
{INF,
0
,
1
,INF,
7
,INF,INF},
{INF,INF,
0
,INF,
6
,
4
,INF},
{INF,INF,
2
,
0
,INF,
5
,INF},
{INF,INF,INF,INF,
0
,INF,
6
},
{INF,INF,INF,INF,
1
,
0
,
8
},
{INF,INF,INF,INF,INF,INF,
0
}};
for
(i=
0
;i<g.n;i++)
//
建立圖9.16所示的圖的鄰接矩陣
for
(j=
0
;j<g.n;j++)
g.edges[i][j]=a[i][j];
Dijkstra(g,
0
);
printf(
"
\n
"
);
}
個(gè)人感覺不太理解，然后想了想，覺得書上這樣解釋有點(diǎn)籠統(tǒng)，不易于理解，于是，自己把自己的理解寫下來。
假設(shè)有圖G，其中有頂點(diǎn)A、B、C、D...，開始利用狄克斯特拉算法從頂點(diǎn)A開始查找最短路徑，首先找到B，如下圖1：
圖1
然后，從【A-C：2】 【B-C：（無窮）】【A-D：1】【B-D：3】中查找權(quán)值最小的也就是A-D，這時(shí)我們可以把A、B（左圓）看成一個(gè)系統(tǒng)AB，然后AB到C的距離是2，到D的距離是1，
所以得到圖2：
圖2
然后把D添加到左圓（已找到最短路徑），如圖3：
圖3
然后得到系統(tǒng)ABD到C的距離是2，然后依次添加頂點(diǎn)，直到右圓為空，即所有頂點(diǎn)均已找到最短路徑。
以上就是狄克斯特拉算法求的從指定頂點(diǎn)（A）到其他頂點(diǎn)最短路徑的算法，其實(shí)里面已經(jīng)包含了求最小生成樹的算法，為什么這樣說呢，請(qǐng)看下面解釋。
圖2中左圓也就是系統(tǒng)AB可以看成一個(gè)只有A和B兩個(gè)頂點(diǎn)的圖，那么AB也就是這個(gè)圖的最小生成樹了，然后現(xiàn)在又添加了頂點(diǎn)D（因?yàn)锳-D、B-D和A-C中最短是A-D也就是頂點(diǎn)D），這時(shí)有兩種選擇
A-D（1）和B-D（3），所以按照最小生成樹法則，選擇A-D（1）作為代表，代表系統(tǒng)（AB）和D的橋梁。這時(shí)形成圖3，而系統(tǒng)AB也變成了系統(tǒng)ABD，而系統(tǒng)ABD同樣還是一個(gè)只有三個(gè)頂點(diǎn)A、B和D的圖的最小生成樹，所以按照狄克斯特拉算法得到的就是指定圖的最小生成樹！
是個(gè)人理解，可能有些愚鈍，肯定有更好地理解方法，望大家指教！
2012.02.21
?
?
風(fēng)箏數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記（3）理解利用狄克斯特拉算法求最小生成樹
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
