二、数据的存储结构：有向连通网络: G ，采用带权邻接矩阵cost[ ][ ]存储
三、算法具体步骤：
设V0是起始源点，U=已求得最短路径终点集合。V-U=未确定最短路径的顶点的集合
(1)初始U={v0}, 辅助数组dist[N]（ 对已经到最短路径终点的顶点 vi ( i U )，vi 所对应的数组分量dist[i]的值为负数；对从v0出发，尚未确定为最短路径终点的顶点vj （j V - U )，vj 所对应的数组分量dist[j]的值为从v0出发，考虑途经已确定为终点的顶点，到达vj ( V - U )的最短路径）。初始时，对j V - U ，有dist[j]=cost[v][j]; 而对U={v}, 则有dist[v]= - cost[v][v] 。
(2)扫描dist[ ]数组，出非0、非负且最小的dist[j]（jV-U)，即从v0出发到vj免费dj网站（jV-U)的路径是最短的。
(3)vj并入U ，则dist[j]=-dist[j]。
(4)调整dist[k](kV-U)，考虑从v0出发，途经vj到达vk是否更短。比较:若-dist[j]+cost[j][k]<di
sk[k], 则dist[k]= -disk[j]+ cost[j][k] 。
(5)重复(2)(3)(4)共 n-1次。
四、源代码：
void dijkstra( int cost[][N], int v ,int t) //起点为v，终点为t
{
int dist[N],i,j,w
for (i=0; i<N; i++)
dist[i]=cost[v][i]; //初始化
dist[v]=-dist[v];
for( i=0; i<N; i++)
{
j=mincost(dist); //非0、非负且最小的dist[j]
if(( j==0)||(j==t));break;
dist[j]=-dist[j]; // vj并入U中
for(k=0;k<N;k++) // 调整dist[k]
if(dist[k]>0) // vk是尚未到达的终点
if(-dist[j]+cost[j][k]<dist[k])
dist[k]=-dist[j]+cost[j][k]; //途经vj到达vk的距离更短
}
for ( i=0; i<N; i++)
if(dist[j]<0)
printf(“%d, %d: %d\n”,v,i,-dist[i]);
}
int mincost( int dist[ ])
// 在V-U 集合中顶点j，dist[j]是dist[ ]中的最小值
{
int i, min, j;
min=MAX;j=0;
for(i=0;i<N;i++)
if(dist[i]>=0&& dist[i]<min)
{min=dist[i];j=i; }
return(j);
}
五、小结
(1) “按路径长度递增顺序”是因为，扩展下一个永久标记节点总是从U中节点的邻接节点中到。
(2) 虽然我们要求的是v0到某个目标节点的最短路径，但是在查这条路径的过程中，我们可能附带的把顶点到其他节点的最短路径也求出来了。
(3) Dijkstra算法包括N-1次的外层循环（每次循环到起点到其中某个结点的最短路径）和两个内层循环，第1个内层循环要经过N次比较来完成对所有结点权值的调整，第2个内层循环从所有结点中出权值最小的未标记结点，并置于U中，此循环也需要经过n次比较以到符合条件的结点。Dijkstra算法的时间复杂度为O(n^2)。
(4) 以邻接矩阵为存储结构的Dijkstra算法是经典的最短路径算法；但是，该算法的实现需要耗费大量的时间和存储空间。目前，已有不少改进算法。比如采用邻接链表作为存储结构，并且为了加快搜索速度，根据距起点的最短路径的权值构造一优先级队列，按照权值大小由小到大排序。另外，从搜索范围角度考虑，Dijkstra算法是一种全向搜索，考虑路网中的每一
(2) 虽然我们要求的是v0到某个目标节点的最短路径，但是在查这条路径的过程中，我们可能附带的把顶点到其他节点的最短路径也求出来了。
(3) Dijkstra算法包括N-1次的外层循环（每次循环到起点到其中某个结点的最短路径）和两个内层循环，第1个内层循环要经过N次比较来完成对所有结点权值的调整，第2个内层循环从所有结点中出权值最小的未标记结点，并置于U中，此循环也需要经过n次比较以到符合条件的结点。Dijkstra算法的时间复杂度为O(n^2)。
(4) 以邻接矩阵为存储结构的Dijkstra算法是经典的最短路径算法；但是，该算法的实现需要耗费大量的时间和存储空间。目前，已有不少改进算法。比如采用邻接链表作为存储结构，并且为了加快搜索速度，根据距起点的最短路径的权值构造一优先级队列，按照权值大小由小到大排序。另外，从搜索范围角度考虑，Dijkstra算法是一种全向搜索，考虑路网中的每一
个道路结点都有可能参与计算，其搜索规模在理论上是以起点为圆心，起点与终点连线长度为半径的圆。而我们在实际生活中规划的最短路径往往是沿着起点指向终点的方向，或者尽量小的偏离该方向。因此控制路网规模是优化的一个角度。
K r u s k a l算法每次选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。K r u s k a l算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。
算法定义
克鲁斯卡尔算法
假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最
小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。
举例描述
初始时没有任何边被选择。边（ 1 , 6）是最先选入的边，它被加入到欲构建的生成树中，得到图1 3 - 1 2 c。下一步选择边（ 3，4）并将其加入树中（如图1 3 - 1 2 d所示）。然后考虑边( 2，7 ，将它加入树中并不会产生环路，于是便得到图1 3 - 1 2 e。下一步考虑边（ 2，3）并将其加入树中（如图1 3 - 1 2 f所示）。在其余还未考虑的边中，（7，4）具有最小耗费，因此先考虑它，将它加入正在创建的树中会产生环路，所以将其丢弃。此后将边（ 5，4）加入树中，得到的树如图13-12g 所示。下一步考虑边（ 7，5），由于会产生环路，将其丢弃。最后考虑边（ 6，5）并将其加入树中，产生了一棵生成树，其耗费为9 9。图1 - 1 3给出了K r u s k a l算法的伪代码。
C代码实现
/* Kruskal.c
Copyright (c) 2002, 2006 by ctu_85
All Rights Reserved.
*/
/* I am sorry to say that the situation of unconnected graph is not concerned */
#include "stdio.h"
#define maxver 10
#define maxright 100
int G[maxver][maxver],record=0,touched[maxver][maxver];
int circle=0;
int FindCircle(int,int,int,int);
int main()
{
int path[maxver][2],used[maxver][maxver];
int i,j,k,t,min=maxright,exsit=0;
int v1,v2,num,temp,status=0;
restart:
printf("Please enter the number of vertex(s) in the graph:\n");
scanf("%d",&num);
if(num>maxver||num<0)
{
printf("Error!Please reinput!\n");
goto restart;
}
for(j=0;j<num;j++)
for(k=0;k<num;k++)
{
if(j==k)
{
G[j][k]=maxright;
used[j][k]=1;
touched[j][k]=0;
}
else
if(j<k)
{
re:
printf("Please input the right between vertex %d and vertex %d,if no edge exists please input -1:\n",j+1,k+1);
发布评论