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