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;