sh实现最小生成树和最短路径的算法

发布网友 发布时间：2022-03-31 02:40

我来回答

共1个回答

热心网友 时间：2022-03-31 04:09

图的最小生成树与最短路径的算法

一、图的生成树与最小生成树
在一个连通图G中，如果取它的全部顶点和一部分边构成一个子图G’，即：

若边集E（G’）中的边既将图中的所有顶点连通又不形成回路，则称子图G’是原图G的一棵生成树。
最小生成树：给图中每个边赋一权值，所有生成树中所选择边的权值之和最小的生成树，称之为最小代价生成树，即是最小生成树。

1、普里姆算法
1.1算法描述
假设G=（V, E）是一个具有n个顶点的连通网，T=（U, TE）是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空集。算法开始时，首先从V中任取一个顶点（假定取v1），将它并入U中，此时U={v1}，然后只要U是V的真子集（即），就从那些其一个端点已在T中，另一个端点仍在T外的所有边中，找一条最短（即权值最小）边，假定为（vi, vj），其中，并把该边（vi, vj）和顶点vj分别并入T的边集TE和顶点集U，如此进行下去，每次往生成树里并入一个顶点和一条边，直到（n-1）次后就把所有n个顶点都并入到生成树T的顶点集中，此时U＝V，TE中含有（n-1）条边，T就是最后得到的最小生成树。 1.2关键问题
普里姆算法的关键之处是：每次如何从生成树T中到T外的所有边中，找出一条最短边。例如，在第k次前，生成树T中已有k个顶点和（k-1）条边，此时T中到T外的所有边数为k（n-k），当然它包括两顶点间没有直接边相连，其权值被看作为“无穷大”的边在内，从如此多的边中查找最短边，其时间复杂性为O（k（n-k）），显然是很费时的。是否有一种好的方法能够降低查找最短边的时间复杂性呢？ 1.3 解决方法
方法是：假定在进行第k次前已经保留着从T中到T外每一顶点（共（n-k）个顶点）的各一条最短边，进行第k次时，首先从这（n-k）条最短边中，找出一条最最短的边（它就是从T中到T外的所有边中的最短边），假设为（vi, vj），此步需进行（n-k）次比较；然后把边（vi, vj）和顶点vj分别并入T中的边集TE和顶点集U中，此时T外只有n-（k+1）个顶点，对于其中的每个顶点vt，若（vj, vt）边上的权值小于已保留的从原T中到vt的最短边的权值，则用（v, vt）修改之，使从T中到T外顶点vt的最短边为（vj, vt），否则原有最短边保持不变，这样，就把第k次后从T中到T外每一顶点vt的各一条最短边都保留下来了。为进行第（k+1）次运算做好了准备，此步需进行（n-k-1）次比较。所以，利用此方法求第k次的最短边共需比较2（n-k）-1次，即时间复杂性为O（n-k）。
1.4 prim算法：
设一个辅助数组closedge，以记录从U到V—U具有最小代价的边。数组中的每个元素closedge[v]是记录类型，包含两个域： closedge[v].lowcast=Min{cost(u,v)|u∈U}; closedge[v].vex存储该边依附的在U中的顶点。
proc mintree_prim(gn:adjmatrix;u0:integer);
begin
for v:=1 to n do
if v<>u0 then
with closedage[v] do [vex:=u0; lowcast:=gn[u0,v];]
closedge[u0].lowcast:=0;{并入U集合}
for i:=1 to n-1 do
begin
v:=min(closedge);{寻找代价最小的边}
write(closedge[v].vex,v); closedge[v].lowcast:=0;{并入U集合}
for k:=1 to n do
if gn[v,k]<closedge[k].lowcast then
begin closedge[k].lowcast:=gn[v,k]; closedge[k].vex:=v; end;
end;
end; 练习1：prim算法实现
【问题描述】从文件中读入连通带权图的信息，按prim算法求出该图的最小生成树，以V1作为初始结点。
【输入文件】第一行两个整数m和n，分别表示图的结点数和图中的边数。以下n行表示n条边：每一行三个数x、y和k，k表示x与y之间边的权值。
【输出文件】共m行，第一行：最小生成树的权；以下m-1行表示选取的边，边的第1个结点小于第2个结点，并按结点由小到大输出。
【示例】输入：5 7 输出：45
1 2 17 1 4
2 3 30 1 5
1 4 5 2 4
2 4 10 3 5
3 4 24
3 5 7
1 5 23

练习2： Eddy painting
Eddy begins to like painting pictures recently ,he is sure of himself to become a painter.Every day Eddy draws pictures in his small room, and he usually puts out his newest pictures to let his friends appreciate. but the result it can be imagined, the friends are not interested in his picture.Eddy feels very puzze,in order to change all friends 's view to his technical of painting pictures ,so Eddy creates a problem for the his friends of you.
Problem descriptions as follows: Given you some coordinates pionts on a drawing paper, every point links with the ink with the straight line, causes all points finally to link in the same place. How many distants does your ty discover the shortest length which the ink draws?
Input：
The first line contains 0 < n <= 100, the number of point. For each point, a line follows; each following line contains two real numbers indicating the (x,y) coordinates of the point.

Input contains multiple test cases. Process to the end of file.
Output：
Your program prints a single real number to two decimal places: the minimum total length of ink lines that can connect all the points.
Sample Input：
3
1.0 1.0
2.0 2.0
2.0 4.0
Sample Output：
3.41

2、克鲁斯卡尔算法
2.1 算法描述
假设G＝（V，E）是一个具有n个顶点的连通网，T＝（U，TE）是G的最小生成树，U的初值等于V，即包含有G中的全部顶点，TE的初值为空。此算法的基本思想是，将图G中的边按权值从小到大的顺序依次选取，若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边，若选取的边使生成树T形成回路，则将其舍弃，如此进行下去，直到TE中包含有n-1条边为止。此时的T即为最小生成树。
2.2 关键问题
克鲁斯卡尔算法的关键之处是：如何判断欲加入的一条边是否与生成树中已选取的边形成回路。这可将各顶点划分为所属集合的方法来解决，每个集合中的顶点表示一个无回路的连通分量。算法开始时，由于生成树的顶点集等于图G的顶点集，边集为空，所以n个顶点分属于n个集合。每个集合中只有一个顶点，表明顶点之问互不连通。
2.3 Kruskal算法：
proc mintree_krusk(gn:adjmatrix);
begin
for i:=1 to n do
un[i]:=i;
for i:=1 to n-1 do
begin
minedge(a,b);
write(a,b,gn[a,b]);
k:=un[b];
for i:=1 to n do {两个连通分量合并}
if un[i]=k then un[i]:=un[a];
end;
end;
2.4 注意：
proc minedge(var a:integer;var b:integer);用于在剩下的边中选取不再同一连通分量上的最小代价的边，边的结点分别为a和b。
为了实现该过程，可以将图中的边生成一边结点（包含两个顶点和代价）数组，由小到大排序，然后通过排序后的数组进行处理；
un数组：用来记载随着边的加入，各顶点属于哪个连通分量。
练习3：Kruskal算法实现
【问题描述】从文件中读入连通带权图的信息，按Kruskal算法求出该图的最小生成树，以V1作为初始结点。
【输入文件】第一行两个整数m和n，分别表示图的结点数和图中的边数。以下n行表示n条边：每一行三个数x、y和k，k表示x与y之间边的权值。
【输出文件】共m行，第一行：最小生成树的权；以下m-1行表示选取的边，按选取边的权值由小到大输出。
【示例】输入：5 7 输出：45
1 2 17 1 4
2 3 30 3 5
1 4 5 2 4
2 4 10 1 5
3 4 24
3 5 7
1 5 23

练习4：判断最小生成树是否唯一
Given a connected undirected graph, tell if its minimum spanning tree is unique.
Definition 1 (Spanning Tree): Consider a connected, undirected graph G = (V, E). A spanning tree of G is a subgraph of G, say T = (V', E'), with the following properties:
1. V' = V.
2. T is connected and acyclic.

Definition 2 (Minimum Spanning Tree): Consider an edge-weighted, connected, undirected graph G = (V, E). The minimum spanning tree T = (V, E') of G is the spanning tree that has the smallest total cost. The total cost of T means the sum of the weights on all the edges in E'.
Input
The first line contains a single integer t (1 <= t <= 20), the number of test cases. Each case represents a graph. It begins with a line containing two integers n and m (1 <= n <= 100), the number of nodes and edges. Each of the following m lines contains a triple (xi, yi, wi), indicating that xi and yi are connected by an edge with weight = wi. For any two nodes, there is at most one edge connecting them.
Output
For each input, if the MST is unique, print the total cost of it, or otherwise print the string 'Not Unique!'.
Sample Input
2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2
Sample Output
3
Not Unique!

二、最短路径
【问题描述】由于从一顶点到另一顶点可能存在着多条路径。每条路径上所经过的边数可能不同，即路径长度不同，我们把路径长度最短（即经过的边数最少）的那条路径叫做最短路径，其路径长度叫做最短路径长度或最短距离。求图中一顶点vi到其余各顶点的最短路径和最短距离比较容易，只要从该顶点vi，出发对图进行一次广度优先搜索遍历，在遍历时记下每个结点的层次即可。
若图是带权图（假定权值非负）从源点vi到终点vj的每条路径上的权（它等于该路径上所经边上的权值之和，称为该路径的带权路径长度）可能不同，我们把权值最小的那条路径也称做最短路径，其权值也称作最短路径长度或最短距离。
实际上，这两类最短路径问题可合并为一类，这只要把第一类的每条边的权都设为1就归属于第二类了，所以在以后的讨论中，若不特别指明，均是指第二类的最短路径问题。
求图的最短路径问题包括两个子问题：一是求图中一顶点到其余各顶点的最短路径，二是求图中每对顶点之间的最短路径。下面分别进行讨论。
始点终点最短路径路径长度
v0v1No path
v2(v0,v2)10
v3(v0,v4,v3)50
v4(v0,v4)30
v5(v0,v4,v3,v5)60

始点终点最短路径路径长度
v1V2(v1,v2)10
V3(v1,v2,v3)27
V4(v1,v5,v4)20
v5(v1,v5)7

1、从一顶点到其余各顶点的最短路径
1.1 描述
迪杰斯特拉（Dijkstra）于1959年提出了解决此问题的一般算法，具体做法是按照从源点到其余每一顶点的最短路径长度的升序依次求出从源点到各顶点的最短路径及长度，每次求出从源点vi到一个终点vj的最短路径及长度后，都要以vj作为新考虑的中间点，用vi到vj的最短路径和最短路径长度对vi到其它尚未求出最短路径的那些终点的当前路径及长度作必要的修改，使之成为当前新的最短路径和最短路径长度，当进行n-2次后算法结束。
1.2 Dijkstra算法:
首先，引进一个辅助向量dist，dist[i]表示当前所找到的从始点V到每个终点Vi的最短路径长度。其初态为：若<v,vi>存在，则dist[i]为其上的权值，否则为最大值（计算机能表示）。
算法:(1)用邻接矩阵cost表示带权有向图。S表示已找到的从v出发的最短路径的终点的集合，初态为空。dist向量的初值为：dist[v,i]=cost[v,i];
(2)选择vj，使得：dist[j]=Min{dist[i]|vi∈V-S}；vj就是当前求得从v出发的最短路径的终点。
S=S+{j};
(3)修改从v出发到集合V-S上任意顶点vk可达的最短路径长度。
if dist[j]+cost[j,k]<dist[k] then dist[k]:=dist[j]+cost[j,k];
(4)重复(2)(3)共n-1次。
代码：proc short_dij;
begin
for i:=1 to n do
begin
dist[i]:=cost[v0,i];
if dist[i]<max then path[i]:=v0 else path[i]:=-1; end;
flag[I]:=true;
for k:=1 to n-1 do
begin
wm:=max; j:=v0;
for i:=1 to n do
if not(flag[i]) and (dist[i]<wm) then begin j:=i; m:=dist[i]; end;
flag[j]:=true; for i:=1 to n do if not(flag[i]) and (dist[j]+cost[j,i]<dist[i]) then
begin dist[i]:=dist[j]+cost[j,i]; path[i]:=j; end;
end;
end; 其中：cost：邻接矩阵；
path[i]：存储从v0到顶点i的最短路径；是以集合作为数组元素；
dist[i]：存储相应路径长度；
flag[i]：表示已处理的顶点。
练习5：Dijkstra算法练习
【问题描述】从文件中读入带权图的信息，按Dijkstra算法根据给定源点求出从源点法到该图中其余顶点的最短路径。
【输入文件】第一行：一个整数L：L=0表示无向图，L=1表示有向图；第二行三个整数m、n和k，分别表示图的结点数、图中的边数以及源点。以下n行表示n条边：每一行三个数x、y和z，z表示x与y之间边的权值。
【输出文件】共m-1行，每一行的数据包括：顶点： 最短路径：路径，如果不存在路径，数据为：顶点：No path。
【示例】输入：1 输出：2：No path
6 8 1 3：10：1 3
1 3 10 4：50：1 5 4
1 5 30 5：30：1 5
1 6 100 6：60：1 5 4 6
2 3 5
3 4 50
4 6 10
5 4 20
5 6 60
练习6：路由选择问题
【问题描述】
X城有一个含有N个节点的通信网络，在通信中，我们往往关心信息从一个节点I传输到节点J的最短路径。遗憾的是，由于种种原因，线路中总有一些节点会出故障，因此在传输中要避开故障节点。
任务一：在己知故障节点的情况下，求避开这些故障节点，从节点I到节点J的最短路径S0。
任务二：在不考虑故障节点的情况下，求从节点I到节点J的最短路径S1、第二最短路径S2。
【输入文件】
第1行： N I J (节点个数 起始节点 目标节点)
第2—N+1行： Sk1 Sk2…SkN (节点K到节点J的距离为SkJ K=1，2，……，N)
最后一行： P T1 T2……Tp (故障节点的个数及编号)
【输出文件】
S0 S1 S2 (S1<=S2 从节点I到节点J至少有两条不同路径)
【输入输出样例】
route.in
5 1 5
0 10 5 0 0
10 0 0 6 20
5 0 0 30 35
0 6 30 0 6
0 20 35 6 0
1 2
route.out
40 22 30

2、每对顶点之间的最短路径
求图中每对顶点之间的最短路径是指把图中任意两个顶点vi和vj（i≠j）之间的最短路径都计算出来。解决此问题有两种方法：一是分别以图中的每个顶点为源点共调用n次迪杰斯特拉算法，此方法的时间复杂性为O（n3）；二是采用下面介绍的弗洛伊德（Floyed）算法，此算法的时间复杂性仍为O（n3），但比较简单。 弗洛伊德算法实际上是一个动态规划的算法。从图的邻接矩阵开始，按照顶点v1，v2，…，vn的次序，分别以每个顶点vk（1≤k≤n）作为新考虑的中间点，在第k-1次运算Ak-1 （A（0）为原图的邻接矩阵G） 的基础上，求出每对顶点vi到vj的最短路径长度计算公式为：

Floyd算法：
proc shortpath_floyd;
begin
for i:=1 to n do for j:=1 to n do
begin
length[i,j]:=cost[i,j];
if length[i,j]<max then path[i,j]:=[i]+[j];
end;
for k:=1 to n do for i:=1 to n do for j:=1 to n do
if length[i,k]+length[k,j]<length[i,j] then
begin
length[i,j]:=length[i,k]+length[k,j];
path[i,j]:=path[i,k]+path[k,j];
end;
end;
其中：cost为邻接矩阵；
path[i,j]：表示顶点i到j的最短路径；
length[i,j]：
练习7：Floyd算法练习
【问题描述】从文件中读入带权图的信息，按Dijkstra算法根据给定源点求出从源点到该图中其余顶点的最短路径。
【输入文件】第一行：一个整数L：L=0表示无向图，L=1表示有向图；第二行三个整数m、n，分别表示图的结点数和图中的边数。以下n行表示n条边：每一行三个数x、y和z，z表示x与y之间边的权值。第n+2行：整数R，以下R行每行一个整数表示顶点标号作为源点。
【输出文件】共R行，每一行的数据表示源点到其余顶点的距离，按顶点编号由小大输出，如果没有路径，输出-1。
【示例】输入：1 输出：-1 10 50 30 60
6 8 -1 –1 –1 20 30
1 3 10
1 5 30
1 6 100
2 3 5
3 4 50
4 6 10
5 4 20
5 6 60
2
1
5追问能够确切一点，重要是切题

追答clear,clc
G=[
inf inf 10 inf 30 100;
inf inf 5 inf inf inf;
inf 5 inf 50 inf inf;
inf inf inf inf inf 10;
inf inf inf 20 inf 60;
inf inf inf inf inf inf;
]; %邻接矩阵
N=size(G,1); %顶点数
v0=1; %源点
v1=ones(1,N); %除去原点后的集合
v1(v0)=0;
%计算和源点最近的点
D=G(v0,:);
while 1
D2=D;
for i=1:N
if v1(i)==0
D2(i)=inf;
end
end
D2
[Dmin id]=min(D2);
if isinf(Dmin),error,end

v0=[v0 id] %将最近的点加入v0集合，并从v1集合中删除
v1(id)=0;

if size(v0,2)==N,break;end
%计算v0（1）到v1各点的最近距离
fprintf('计算v0（1）到v1各点的最近距离\n');v0,v1
id=0;
for j=1:N %计算到j的最近距离
if v1(j)
for i=1:N
if ~v1(i) %i在vo中
D(j)=min(D(j),D(i)+G(i,j));
end
D(j)=min(D(j),G(v0(1),i)+G(i,j));
end
end
end
fprintf('最近距离\n');D
if isinf(Dmin),error,end
end
v0