vj算法网

① Dijkstra算法流程图

定义G=(V,E)，定义集合S存放已经找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点，即有T=V-S

Dijkstra算法描述如下：

(1) 假设用带权的邻接矩阵edges来表示带权有向图，edges[i][j]表示弧<Vi, Vj>上的权值。若<Vi, Vj>不存在则置edges[i][j]=∞（计算机上用一个允许的最大值代替）。S为已经找到的从Vs出发的最短路径的终点集合，它初始化为空集。那么，从Vs出发到图上其余各顶点（终点）Vi可能达到的最短路径长度的初值为：D[i]=deges[s][i] Vi∈V

(2) 选择Vj，使得D[j]=Min{D[i]|Vi∈V-S}，Vj就是当前求得的一条从Vs出发的最短路径的终点。令S=S∪{Vj}

(3) 修改从Vs出发到集合V-S上任一顶点Vk可达的最短路径长度。如果D[j]+edges[j][k]<D[k]则修改D[k]为D[k]=D[j]+edges[j][k]

重复操作(2)(3)共n-1次。由此求得从Vs到图上其余各顶点的最短路径。

② 关键路径怎么求求详解。

关键路径的算法是建立在拓扑排序的基础之上的，这个算法中用到了拓扑排序。

1． 什么是拓扑排序？

举个例子先：一个软件专业的学生学习一系列的课程，其中一些课程必须再学完它的基础的先修课程才能开始。如：在《程序设计基础》和《离散数学》学完之前就不能开始学习《数据结构》。这些先决条件定义了课程之间的领先(优先)关系。这个关系可以用有向图更清楚地表示。图中顶点表示课程，有向边表示先决条件。若课程i是课程j的先决条件，则图中有弧<i,j>。若要对这个图中的顶点所表示的课程进行拓扑排序的话，那么排序后得到的序列，必须是按照先后关系进行排序，具有领先关系的课程必然排在以它为基础的课程之前，若上例中的《程序设计基础》和《离散数学》必须排在《数据结构》之前。进行了拓扑排序之后的序列，称之为拓扑序列。

2． 如何实现拓扑排序？

很简单，两个步骤：

1． 在有向图中选一个没有前驱的顶点且输出。

2． 从图中删除该顶点和以它为尾的弧。

重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。

3． 什么是关键路径？

例子开头仍然，图1是一个假想的有11项活动的A0E-网。其中有9个事件v1,v2......，v9，每个事件表示在它之前的活动一完成，在它之后的活动可以开始。如v1表示整个工程的开始，v9表示整个工程结束，v5表示a4和a5已完成，a7和a8可以开始。与每个活动相联系的数是执行该活动所需的时间。比如，活动a1需要6天，a2需要4天。

packagegraph;
importjava.util.*;
publicclassGrph_CriticalPath
{
Graph_AdjListadjList;
Stack<Integer>T=newStack<Integer>();
intve[];
intvl[];
finalintmax=10000;

publicGrph_CriticalPath(Graph_AdjListadjList)//图的存储结构是用的邻接表
{
this.adjList=adjList;
intlength=adjList.vetexValue.length;
ve=newint[length];
vl=newint[length];
for(inti=0;i<length;i++)
{
ve[i]=0;
vl[i]=max;
}
}

publicvoidgetCriticalPath()
{
topologicalOrder();

intt=T.pop();
T.push(t);
vl[t]=ve[t];
while(!T.isEmpty())
{
intj=T.pop();
for(Graph_AdjList.ArcNodep=adjList.vetex[j].firstArc;p!=null;p=p.next)
{
intk=p.adjvex;
if(vl[k]-p.weight<vl[j])
{
vl[j]=vl[k]-p.weight;
}
}
}
for(inti=0;i<ve.length;i++)
{
for(Graph_AdjList.ArcNodep=adjList.vetex[i].firstArc;p!=null;p=p.next)
{
intk=p.adjvex;
intee=ve[i];
intel=vl[k]-p.weight;
if(ee==el)
{
System.out.print(i+","+k+"");
}

}
}
}

publicvoidtopologicalOrder()
{
Stack<Integer>S=newStack<Integer>();
S.push(0);
intcount=0;
while(!S.isEmpty())
{
intj=S.pop();
T.push(j);
count++;
Graph_AdjList.ArcNodep=null;
for(p=adjList.vetex[j].firstArc;p!=null;p=p.next)
{
intk=p.adjvex;
if(--adjList.degree[k]==0)
{
S.push(k);
}
if(ve[j]+p.weight>ve[k])
{
ve[k]=ve[j]+p.weight;
}
}
}
if(count<adjList.vetexValue.length)
{
System.out.println("图中存在环路！");
return;
}
}

publicvoidprint()
{
while(!T.isEmpty())
{
System.out.print(T.pop()+"");
}
}

publicvoidprintVel()
{
System.out.println();
for(inti=0;i<ve.length;i++)
{
System.out.print(ve[i]+"");
}
System.out.println();
for(inti=0;i<vl.length;i++)
{
System.out.print(vl[i]+"");
}
}


}

转自：http://blog.csdn.net/pigli/article/details/5777048

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

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

一、图的生成树与最小生成树
在一个连通图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就归属于第二类了，所以在以后的讨论中，若不特别指明，均是指第二类的最短路径问题。
求图的最短路径问题包括两个子问题：一是求图中一顶点到其余各顶点的最短路径，二是求图中每对顶点之间的最短路径。下面分别进行讨论。
始点 终点 最短路径 路径长度
v0 v1 No path
v2 (v0,v2) 10
v3 (v0,v4,v3) 50
v4 (v0,v4) 30
v5 (v0,v4,v3,v5) 60

始点 终点 最短路径 路径长度
v1 V2 (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

④ 迪杰斯特拉算法的算法实现

· 算法思想
设给定源点为Vs，S为已求得最短路径的终点集，开始时令S={Vs} 。当求得第一条最短路径(Vs ，Vi)后，S为{Vs，Vi} 。根据以下结论可求下一条最短路径。
设下一条最短路径终点为Vj ，则Vj只有：
◆ 源点到终点有直接的弧<Vs，Vj>；
◆ 从Vs 出发到Vj 的这条最短路径所经过的所有中间顶点必定在S中。即只有这条最短路径的最后一条弧才是从S内某个顶点连接到S外的顶点Vj 。
若定义一个数组dist[n]，其每个dist[i]分量保存从Vs 出发中间只经过集合S中的顶点而到达Vi的所有路径中长度最小的路径长度值，则下一条最短路径的终点Vj必定是不在S中且值最小的顶点，即：
dist[i]=Min{ dist[k]| Vk∈V-S }
利用上述公式就可以依次找出下一条最短路径。
· 示例程序
· 算法思想
var a:array[1..100,1..100]of integer;//邻接矩阵
flag:array[1..100] of boolean;//已经找到最短路径的节点标志
path:array[1..100]of integer;
w,x,n,i,j,min,minn,k:integer;
begin
readln(n,k);for i:=1 to n do//读取邻接矩阵,无路径写-1
begin
for j:=1 to n do
begin
read(a[i,j]);
If a[i,j]=-1 then a[I,j]:=maxint;
end;
readln;
end;
fillchar(flag,sizeof(flag),false);//标明所有节点都未找到最短路径
flag[k]:=true; //源节点除外
fillword(path,sizeof(path) div 2,k);
path[k]:=0;
minn:=k;//标记最小的点for x:=2 to n do
begin
min:=32767;//标记要找下一个最短路径点的距离
for i:=1 to n do//找下一点点
if (a[k,i]<min) and (flag[i]=false) then
begin
min:=a[k,i];
minn:=i;
end;
flag[minn]:=true;//标记下一个点的找到
for j:=1 to n do //更新最短路径
if (j<>minn) and (a[k,minn]+a[minn,j]<a[k,j]) and (flag[j]=false) then
begin
a[k,j]:=a[k,minn]+a[minn,j];
path[j]:=minn;
end;
end;
for i:=1 to n do write(a[k,i],' ');//输出源点到各个点的距离
writeln;
for i:=1 to n do write(path[i],' ');//输出源点到各个点的距离
end.
求采纳（空格被网络吃了……）

⑤ Floyd算法的算法过程

1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。
把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i,j]=d，d表示该路的长度；否则G[i,j]=无穷大。定义一个矩阵D用来记录所插入点的信息，D[i,j]表示从Vi到Vj需要经过的点，初始化D[i,j]=j。把各个顶点插入图中，比较插点后的距离与原来的距离，G[i,j] = min( G[i,j], G[i,k]+G[k,j] )，如果G[i,j]的值变小，则D[i,j]=k。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。
比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为{V5,V3,V1}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。

⑥ 用弗洛伊德算法求最短路径

是地信的题吧，先给你说v1怎么求，
先找出v1能去的最近的点，为V2，
如果S1i>S12+S2i
修改V1到Vi的距离为S12+S2i
然后去掉V2，在其余的点中找距V1最近的，按上面的方法修改
最后得到V1与其他各点的最短距离
同样的方法求出到其他点的最短距离

⑦ Warshall算法的算法介绍

1、引言
Warshall在1962年提出了一个求关系的传递闭包的有效算法。其具体过程如下，设在n个元素的有限集上关系R的关系矩阵为M：
（1）置新矩阵A=M;
（2）置k=1;
（3）对所有i如果A[i,k]=1，则对j=1..n执行：
A[i,j]←A[i,j]∨A[k,j];
（4）k增1;
（5）如果k≤n，则转到步骤（3），否则停止。
所得的矩阵A即为关系R的传递闭包t(R)的关系矩阵。
在左孝凌等编着的《离散数学》中提到了该算法，但并未对此算法作出解释。下面本文将对该算法的思想作出一种比较通俗的解说。
2、对Warshall算法的解说
设关系R的关系图为G，设图G的所有顶点为v1,v2,…,vn，则t(R)的关系图可用该方法得到：若G中任意两顶点vi和vj之间有一条路径且没有vi到vj的弧，则在图G中增加一条从vi到vj的弧，将这样改造后的图记为G’，则G’即为t(R)的关系图。G’的邻接矩阵A应满足：若图G中存在从vi到vj路径，即vi与vj连通，则A[i,j]=1，否则A[i,j]=0。
这样，求t(R)的问题就变为求图G中每一对顶点间是否连通的问题。
定义一个n阶方阵序列A(0),A(1),A(2),…,A(n)，每个方阵中的元素值只能取0或1。A(m)[i,j]=1表示存在从vi到vj且中间顶点序号不大于m的路径（m=1..n），A(m)[i,j]=0表示不存在这样的路径。而A(0)[i,j]=1表示存在从vi到vj的弧，A(0)[i,j]=0表示不存在从vi到vj的弧。
这样，A(n)[i,j]=1表示vi与vj连通，A(n)[i,j]=0表示vi与vj不连通。故A(n)即为t(R)的关系矩阵。
那么应如何计算方阵序列A(0),A(1),A(2),…,A(n)呢？
很显然，A(0)=M（M为R的关系矩阵）。
若A(0)[i,1]=1且A(0)[1,j]=1，或A(0)[i,j]=1，当且仅当存在从vi到vj且中间顶点序号不大于1的路径，此时应将A(1)[i,j]置为1，否则置为0。
一般地，若A(k-1)[i,k]=1且A(k-1)[k,j]=1，或A(k-1)[i,j]=1，当且仅当存在从vi到vj且中间顶点序号不大于k的路径，此时应将A(k)[i,j]置为1，否则置为0（k=1..n）。用公式表示即为：
A (k)[i,j]=(A(k-1)[i,k]∧A(k-1)[k,j])∨A(k-1)[i,j] i,j,k=1..n
这样，就可得计算A(k)的方法：先将A(k)赋为A(k-1)；再对所有i=1..n，若A(k)[i,k]=1（即A(k-1)[i,k]=1），则对所有j=1..n，执行：
A (k)[i,j]←A(k)[i,j]∨A(k-1)[k,j]
但这与前述Warshall算法中的第（3）步还有一定距离。若将上式改为：
A(k)[i,j]←A(k)[i,j]∨A(k)[k,j] （即把A(k-1)[k,j]改为A(k)[k,j]）
就可将上标k去掉，式子就可进一步变为：
A[i,j]←A[i,j]∨A[k,j]
这样可以只用存储一个n阶方阵的空间完成计算，且与前述Warshall算法中第（3）步的式子一致。那么，可不可以把A(k-1)[k,j]改为A(k)[k,j]呢？答案是肯定的。下面将证明在计算A(k)的过程中A(k-1)[k,j]与A(k)[k,j]相等（A(k)被赋初值A(k-1)后）。考察计算A(k)的方法 只有当i=k时A(k)[k,j]的值才有可能改变，此时将式A(k)[i,j]←A(k)[i,j]∨A(k-1)[k,j]中的i换为k，得A(k)[k,j]←A(k)[k,j]∨A(k-1)[k,j]，对某一j，执行该式的赋值操作前A(k)[k,j]=A(k-1)[k,j]，因为计算A(k)开始时A(k)被赋为A(k-1)，故它们相或的结果等于A(k-1)[k,j]，故赋值操作不改变A(k)[k,j]的值。这样，就没有操作会改变A(k)[k,j]的值，故A(k-1)[k,j]与A(k)[k,j]相等。
综上，就可得到计算A(n)的算法，且该算法与前述的Warshall算法完全一致。
由上面的分析，不难看出，Warshall算法类似于求图中每对顶点间最短路径的Floyd算法。其实，用Floyd算法也能求关系的传递闭包，方法为令关系R的关系图G中的每条弧的权值都为1，这样得一有向网G1，设G1的邻接矩阵为D(-1)（若vi无自回路，则D(-1)(i,i)=∞），对G1用Floyd算法求其每对顶点间最短路径，得结果矩阵D(n-1)。因若G中vi与vj连通，当且仅当D(n-1)[i,j]≠∞，故将矩阵D中的∞都改为0，其它值都改为1，得矩阵A，则矩阵A即为t(R)的关系矩阵。Floyd算法和Warshall算法的时间复杂度都为O(n3)，但明显用Floyd算法求关系的传递闭包绕了弯子。
参考文献：
[1]左孝凌，李为鉴，刘永才，《离散数学》，上海：上海科学技术文献出版社，1982
[2]严蔚敏，吴伟民，《数据结构 C语言版》，北京：清华大学出版社，1997

⑧ 编写一个在有向图G的邻接表存储表示中删除一条边<Vi,Vj>的算法，并分析算法的时间复杂度。

删边i-j
邻接矩阵：
邻接表：
有向图：
p = v[i] -> firstedge；
pre = p;
while (p && p -> data != j)
{pre = p;p = p -> next;}
if (p && pre == p) v[i] -> firstedge = p -> next;
else if (p) pre -> next = p -> next;