最短路徑演算法完整源代碼

⑴ 最短路徑演算法 C語言

#include<stdio.h>

#defineMAXNODE108

intpath[MAXNODE+1][MAXNODE+1]={0};

intmain(void)
{
FILE*fpr,*fpw;
intva,vb,i,j,k;

fpr=fopen("in.txt","r");/*讀取的文件名稱in.txt*/
fpw=fopen("out.txt","w");/*path的數據在out.txt中展現*/

while(fscanf(fpr,"%d%d",&va,&vb)!=EOF)
path[va][vb]=path[vb][va]=1;

for(k=1;k<=MAXNODE;++k){
for(i=1;i<=MAXNODE;++i){
for(j=1;j<=MAXNODE;++j){
if(!path[i][k]||!path[k][j])
continue;

if(!path[i][j])
path[i][j]=path[i][k]+path[k][j];
elseif(path[i][j]>path[i][k]+path[k][j])
path[i][j]=path[i][k]+path[k][j];
}
}
}

for(i=1;i<=MAXNODE;++i){
for(j=1;j<=MAXNODE;++j){
if(i==j)
fprintf(fpw,"%-10d",0);
elseif(path[i][j])
fprintf(fpw,"%-10d",path[i][j]);
else
fprintf(fpw,"%-10d",-1);
}
fprintf(fpw,"
");
}

return0;
}

注意：floyd演算法中k為最外層，這是動態規劃的思想，不能改變i,j,k的順序！！！

這是之前的答案的錯誤之處。

-1表示不通。

具體程序分析，我可以加你QQ，願意的話，你把QQ寫給我。

⑵ 尋找最短路徑的匯編語言實現源代碼是什麼(用Dijkstra 演算法)

Dijkstra演算法Dijkstra演算法是典型的最短路徑演算法，用於計算一個節點的最短路徑中的所有其他節點。其主要特點是出發點為中心向外層層擴展，直到擴展到結束日期。 Dijkstra最短路徑演算法能得出最佳的解決方案，但許多節點，它遍歷計算，這樣的效率是低的。最短路徑演算法的
Dijkstra演算法是非常有代表性的許多專業課程的基本內容進行了詳細的介紹，如數據結構，圖論，運籌學，等等。
Dijkstra演算法的一般性發言一般有兩種方式，永久和臨時的標簽，開啟，關閉表的方式之一，德魯表示，為了引進和下面的A *演算法和D *演算法一致，這里是開放的，關閉表。
貪婪的方法，演算法策略
大概過程如下：
創建兩個表，打開，關閉。
OPEN表保存沒有調查之前已產生的所有節點，CLOSED表中記錄已訪問過的節點。
1。的道路網路的出發點和等待在公開組的檢查沒有檢查點，此點。
2。打開表，以找出從起點最近的點，以確定所有的子節點，這一點，這點上關閉表。
3。遍歷訪問這個點的子節點。獲得這些子節點從子節點到OPEN表的放電的開始點的距離的值。
4。重復步驟2和步驟3，直到OPEN表為空，或找到目標點。
[編輯本段]演算法是
包括的文件
定義MAXNUM 765432100的
使用命名空間std;
ifstream的散熱片（Dijkstra演算法。在「）;
ofstream這樣的FOUT（」Dijkstra.out「）;
詮釋地圖[501] [501];
布爾is_arrived [501];
詮釋區[501] [501]，堆棧[501];
整數P，Q，K，路徑，源代碼，頂點，溫度，SetCard
詮釋FindMin（）
{
詮釋P，溫度= 0，MINM = MAXNUM;
（P = 1，P <=頂點，P + +）
（（區[P] MINM）&&（！is_arrived [P] ））
{
MINM區[P]。
溫度= P;
}
收益溫度;
}
：（ ）
{
的memset（is_arrived，0，大小（is_arrived））;
鰭>>源代碼>>頂點;
（P = 1，P <=頂點，P + +）
（Q = 1，Q =頂點，Q + +）
{
鰭>>地圖[P] [Q];
（圖[ P] [Q] == 0）地圖[P] [Q] = MAXNUM;
}
為（P = 1，P <=頂點，P + +）
{ />區[P] =地圖[來源] [P];
（區[P]！= MAXNUM）
[P] =源;
其他
[P] = P;
}
is_arrived [來源] = TRUE;
SetCard = 1;

{
溫度= FindMin（）;
（Temp! = 0）
{
SetCard SetCard +1;
is_arrived [溫度] = TRUE;
（P = 1，P <=頂點，P + +）
（（區[P]>區[溫度] +地圖[溫度] [P]）&&（！is_arrived [P]））
{
區[P] =區[溫度] +地圖[溫度] [P]
[P] =溫度;
}
}
其他
突破; BR />}
（SetCard! =頂點）;
（P = 1，P <=頂點，P + +）
（p! =源）
{
FOUT <<「======================== \ n」;
FOUT <<「來源：」<; <資料來源<<「\ n目標：」「P <<'\ n';
（區[P] == MAXNUM）
{
FOUT <<」距離：「< 「無限\ n」;
FOUT <<「路徑：沒辦法！」;
}
其他
{
FOUT「距離」：「<<區[P] <<'\ n';
K = 1;
路徑= P;
同時（從[路徑]！=路徑）
{
棧[K] =路徑;
路徑=從[路徑];
K = K +1;
}
FOUT <<「路徑：」<（Q = K-1，Q = 1，Q - ）
FOUT「 - >」<<棧[問];
}
FOUT <<「\ ?======================== \ n \ n「;}

fin.close（）;
fout.close（）;
返回0;
}
樣品輸入
2
7
00 20 50 30 00 00 00
20 00 25 00 00 70 00
50 25 00 40 25 50 00
30 00 40 0??0 55 00 00
00 00 25 55 00 10 00
00 70 50 00 10 00 00
00 00 00 00 00 00 00
樣本輸出
========================
來源：2
目標：1
距離：20
路徑：2 - > 1
==================== ====
========================
來源：
目標：3
距離：25
路徑：2 - > 3 ========================

===== ===================
來源：
目標：4
距離：50
路徑：2 - > 1 - > ======================== 4

============== =========
來源：
目標：5
距離：50
路徑：2 - > 3 - > 5
== ======================
========================
來源：
目標：6
距離：60
路徑：2 - > 3 - > 5 - > 6
========= ===============
========================
來源：2
目標：7
距離：無限
路徑：沒辦法！
========================
示常式序和相關子程序如下：
無效的Dijkstra（INT N，INT [ ]距離的int [] iPath標）
{
詮釋最短距離，U
INT I，J;
/ /從n個頂點的鄰接矩陣的副本可以擺脫行了，是復制前n行的距離[]
（i = 0;我VerNum，我+ +）
{
距離=圓弧[N];
訪問= 0;
} / / n個結點訪問，因為n個頂點的出發點是
訪問[N] = 1;
/ /找到的頂點其他頂點的路線，並且它不是頂點n的開頭，沒有先前旅遊。
/ /相當於u點，這一點是沒有的出發點N（i = 0; I <VerNum，我+ +）
{
U = 0

最短距離=否;
為（J = 0; <VerNum; + +）
（訪問[J] == 0 &&（距離[J]最短距離））
{
最短距離=距離[J];
ü= J;
}
/ /例如P1871圖G6距離=無，無，無，30,100]第一次看的是V2，U = 2
/ /找到結束，的MinDis意味著它無法連接，然後返回。這種情況是相似的V5。

（最短距離==否）返回;
/ /建立一個u個頂點將被用於頂點u，相當於弧[V，U +弧U，W] 。
訪問[U] = 1;
/ /找到一個U頂點到所有其他頂點最小的路徑實際上是在尋找弧] [U，J，J值在[0， VerNum]。
/ /如果是圓弧，U [I] +凱旋門[U，J] ARC [I，J]，ARC [I，J] =弧[I，U] +凱旋門[U J] <弧[I，J]
/ /的做法，因為距離[]是期望的結果，起始點確定的情況下，那就是：

/ /如果（距離[U] +圓弧[U，J）<=距離[J]：
/ /距離[J]距離[U] + [U，J弧];
/ /保存iPath標[] u點數量;
/ /同樣，設置訪問量：新發現的路由[J] = 0，經過尋找另一條道路，這條道路可能不利用。 V3
（J = 0; <VerNum; + +）
（訪問[J] == 0 &&弧U，J] <&& U！= J） /> {
（（距離[U] +圓弧[U，J）<=距離[J]）
{
距離[J]距離[U] +弧[ U，J];
訪問[J] = 0;
iPath標[J] = U;
}
}
}
} / /輔助功能
無效的Prim（），
{
INT I，M，N = 0;
為（i = 0;我VerNum;我+ +）
{
訪問= 0;
T =新的TreeNode（）;
T.Text = V;
}
訪問[N] + +;
listBox1.Items。添加（V [N]）;
（參觀（）> 0）
{
（（M = MinAdjNode（N））！= -1）
{ BR /> T [N]。 Nodes.Add（T [M]）;
N = M;
訪問[N] + +;
}
其他
{
?= MinNode（0）;
（N> 0）T [旻]。 Nodes.Add（T [敏]）;
訪問[N] + +;
}
listBox1.Items.Add（V [N]）;
} treeView1.Nodes.Add（T [0]）;
}
的無效TopoSort（）
{
INT I，N;
listBox1.Items.Clear（ ）;
棧S =新的堆棧（）;
為（i = 0;我VerNum，我+ +）
訪問= 0;
為（= VerNum- 1> = 0; I - ）
（入度（I）== 0）
{
S.Push（I）;
訪問+ +; ...... />}
而（S.Count！= 0）
{
N =（INT）S.Pop（）;
listBox1.Items.Add（V [N] ）;
CLEARLINK（N）;
為（i = VerNum-1> = 0; I - ）
（分== 0 &&入度（I）== 0）
{
S.Push（I）;
訪問+ +;
}
}
}
無效AOETrave（INT N，樹節點TR，W）
{
INT I，W0;
（出度（N）== 0）返回;
（i = 0; <VerNum; + +）
（（W0 =圓弧[N，I]）！= 0）
{
listBox1.Items.Add（V +「\ t」+（W + W0）的ToString（）+「\ t」+ i.ToString（）+「\ t」+ n.ToString（））;
TreeNode的T1 =新的TreeNode（）;
T1.Text = V + 「W =」+（W + W0）。的ToString（）+「]」;
TR.Nodes.Add（T1）;
AOETrave（I，T1，W + W0）;
}
}
無效AOE（）
{
INT I，W = 0，M = 1;
TreeNode的T1 =新的TreeNode（）;
為（i = 0; <VerNum;我+ +）
{
訪問= 0;
}
T1.Text = V [0];
listBox1.Items.Add（「父母符號顯示生成樹：「）;
listBox1.Items.Add（」V \ TW \工業貿易署\ TPID「）;
為（i = 0;我VerNum，我+ +）
{
（（W =弧[0，I]）！= 0）
{
listBox1.Items.Add（V +「\ t」+ w.ToString（）+「\ T「+ i.ToString（）+」\ T0「）;
TreeNode的T2 =新的TreeNode（）;
T2.Text = V +」W =「+ w.ToString（）+」 「;
AOETrave（I，T2，W）;
listBox1.Items.Add（」\ t \ t樹「+ m.ToString
T1.Nodes.Add（ T2），（））;
米+ +;
}
}
treeView1.Nodes.Clear（）;
treeView1.Nodes.Add（T1）;
}
IsZero（）
{
我;
為（i = 0;我VerNum，我+ +）
（LineIsZero （一）> = 0）返回;
返回-1;
}
詮釋LineIsZero（N）
{
我
（i = 0; <VerNum;我+ +）
（電弧[N，I] = 0）返回;
返回-1;}

：無效DepthTraverse（）
{
INT I，M;
（i = 0; <VerNum，我+ +）
{
訪問= 0; BR /> T =新的TreeNode（）;
T.Text = V
R = 0;
}
而（（M = IsZero（））> = 0）
{
（訪問[M] == 0）
{
listBox1.Items.Add（V [M]）;
R [M] = 1 ;}

訪問[M] + +;
DTrave（M）;
}
為（i = 0; {
（R == 1）
treeView1.Nodes.Add（T）;
}
}
無效DTrave（N） /> {
我;
（LineIsZero（N）<0）返回;
為（i = VerNum-1> = 0; I - ）
（弧[N] = 0）
{
弧[N，I] = 0;
弧[I，N] = 0;
（訪問= = 0）
{
listBox1.Items.Add（V）;
T [N]。 Nodes.Add（T）;
R = 0;
}
訪問+ +;
DTrave（I）;
}
} ：無效BreadthTraverse（）
{
INT I，M;
（i = 0; <VerNum，我+ +）
{
訪問= 0;
T =新的TreeNode（）;
T.Text = V;
R = 0;
}
而（（M = IsZero（））> = 0 ）
{
（訪問[M] == 0）
{
listBox1.Items。添加（V [M]）;
R [M] = 1;
}
訪問[M] + +;
BTrave（M）;
} BR />（i = 0;我VerNum，我+ +）
{
（R == 1）
treeView1.Nodes.Add（T）;
}
}
無效BTrave（N）
{
我
隊列Q =新的Queue（）;
Q.Enqueue（N）
而（Q.Count！= 0）
{
為（i = 0;我VerNum，我+ +）
{
（電弧N，I] = 0）
{
弧[N，I] = 0;
弧[N] = 0;
（訪問== 0）
{
listBox1.Items.Add（V）;
T [N]。 Nodes.Add（T）;
直徑= 0;
}
訪問+ +;
Q.Enqueue（I）;
}
} BR /> N =（int）的Q.Dequeue（）;
}
}
詮釋MinNode（VN）
{
INT I，J，N，米，最小=否;
N = -1，M = -1;
為（i = VN我VerNum，我+ +）
中for（j = 0; J < VerNum; + +）
（電弧[I，J] = &&弧[I，J]閔&&分== 0 &&訪問[J] == 1）
{ BR />最小值=弧[I，J]; N = I，M = J;
}
敏=旻= M
返回n;
} BR />詮釋MinAdjNode（N）
{
我，敏，米;
最小值=否，M = -1;
（i = 0; I < VerNum，我+ +）
（電弧[N，I] =沒有訪問&& == 0 &&最小弧[N，I] &&訪問[N] == 1）{BR /> BR />最小值=弧[N，I]，M = I;}

返回米;
}
INT訪問（）
{
INT I，S = 0;
為（i = 0; <VerNum，我+ +）
（訪問== 0）+ +;
返回s;
>}

[編輯本段] Dijkstra演算法的Pascal實現：
程序Dijkstra的;
VAR
答：ARRAY [1 .. 100,1 .. 100的整數;
標志：數組[1] .. 100]布爾值;
W，X，N，I，J，分，明尼蘇達州：整數;
開始
readln（N）;
我：= 1到n
開始
對於j = 1到n
讀（A）;
readln;
結束;
fillchar（標志中，sizeof（標志），假）;
標志[1]：= TRUE;
明尼蘇達州：= 1;
為：= 2到n
開始
分： 32767;
W：=明尼蘇達州
我：= 1到n做
（W >）和（[W，I] <MIN），然後
開始
分：= [];
明尼蘇達州：= I;
結束;
標志[明尼蘇達州]：= TRUE;
J： 1到n做
（J >明尼蘇達州）和（A [1，明尼蘇達州] + A [明尼蘇達州，J]，A [1，J）和（標志[J] = FALSE），那麼 BR /> A [1，J] = [1，明尼蘇達州] + A [明尼蘇達州，J];
結束;
我：= 1到n做
寫（ [1]）;
年底。

⑶ 最短路徑代碼

#include<iostream.h>

// 定義 狀態代碼 及 數據類型
#define NULL 0
#define OK 1
#define ERROR 0
#define INFINITY 255
#define MAX_VERTEX_NUM 20

typedef int Status;
typedef int ElemType;

// ----------------------- 隊列結構 -------------------------

// 節點存儲結構
typedef struct QNode{
ElemType data;
struct QNode *next;
}QNode,*QueuePtr;

// 隊列
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;

// 初始化隊列
Status InitQueue(LinkQueue &Q){
Q.front=Q.rear=new QNode;
if(!Q.front)
return ERROR;
Q.front->next=NULL;
return OK;
}

// 入隊
Status EnQueue(LinkQueue &Q,ElemType e){
QueuePtr p=NULL;
p=new QNode;
if(!p)
return ERROR;
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}

// 出隊
Status DeQueue(LinkQueue &Q,ElemType &e){
QueuePtr p=NULL;
if(Q.front==Q.rear)
return ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p) // 注意當出隊後為空隊的情況
Q.rear=Q.front;
delete p;
return OK;
}

// 判斷是否為空隊列
Status EmptyQueue(LinkQueue &Q){
return Q.front==Q.rear?true:false;
}

// 復制隊列( Q1 to Q2)
Status CopyQueue(LinkQueue &Q1,LinkQueue &Q2){
int e;
QueuePtr p;
while(!EmptyQueue(Q2)){ // clean Q2
DeQueue(Q2,e);
} // one by one
p=Q1.front->next;
while(p){
e=p->data;
p=p->next;
EnQueue(Q2,e);
}
return OK;
}

// ---------------------- 圖的結構：鄰接矩陣（有向網） --------------------------//

// 鄰接矩陣元素
typedef struct ArcCell{
int adj; // arc value: >0, INFINITY: no link
char *info;
}AcrCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

// 圖的結構
typedef struct{
char vexs[MAX_VERTEX_NUM][5]; // 頂點數組
AdjMatrix arcs; // 鄰接矩陣
int vexnum; // 圖當前的頂點數
int arcnum; // 圖當前邊的個數
}MGraph;

// 建立鄰接圖（key=1為有向網，key=0為無向網）
Status CreateUDN(MGraph &G,int vexnum,int edgenum,char *names,char *edges,int key){
int i,j,k,value;
// 輸入當前圖的頂點數，邊個數
G.vexnum=vexnum;
G.arcnum=edgenum;
// 各個頂點數據
for(i=0;i<G.vexnum;++i){
for(j=0;j<4;j++){
G.vexs[i][j]=*names;
names++;
}
G.vexs[i][4]='\0';
}
// 初始化鄰接矩陣（全為INFINITY）
for(i=0;i<MAX_VERTEX_NUM;++i){
for(j=0;j<MAX_VERTEX_NUM;++j){
G.arcs[i][j].adj=INFINITY;
G.arcs[i][j].info=NULL;

}
}
// 建立鄰接矩陣每條邊的數值
for(k=0;k<G.arcnum;++k){
i=int(*edges)-48;
edges++;
j=int(*edges)-48;
edges++;
value=(int(*edges)-48)*10;
edges++;
value+=int(*edges)-48;
edges++;
G.arcs[i][j].adj=value;
if(!key){
G.arcs[j][i].adj=value;
}
}
return OK;
}

// 列印出鄰接矩陣
void PrintGraph(MGraph &G){
int i,j;
cout<<"\n//--------------- PrintMatrix -----------------//\n\n ";
for(i=0;i<G.vexnum;++i){
cout<<G.vexs[i]<<" ";
}
cout<<endl;
for(i=0;i<G.vexnum;++i){
cout<<"\n\n"<<G.vexs[i]<<" ";
for(j=0;j<G.vexnum;++j){
if(G.arcs[i][j].adj==INFINITY)
cout<<" / ";
else
cout<<" "<<G.arcs[i][j].adj<<" ";
}
}
cout<<"\n\n//--------------- PrintMatrix -----------------//\n";
}

// ---------------------- 求源點v0到各點的最短路徑 --------------------------//

void ShortestPath(MGraph &G,int v0){
int D[MAX_VERTEX_NUM],final[MAX_VERTEX_NUM],i,w,v=0,min;
// 建立隊列數組，用以依次儲存最短的路徑
LinkQueue Q[MAX_VERTEX_NUM];
// 初始化數組
for(i=0;i<G.vexnum;++i){
InitQueue(Q[i]);
D[i]=G.arcs[v0][i].adj;
final[i]=false;
}
final[v0]=true;
// 一個一個循環找出最短距離（共vexnum－1個）
for(i=1;i<G.vexnum;++i){
min=INFINITY;
// 掃描找出非final集中最小的D[]
for(w=0;w<G.vexnum;++w){
if(!final[w] && D[w]<min){
v=w;
min=D[w];
}
}
final[v]=true;
// 更新各D[]數據
for(w=0;w<G.vexnum;++w){
if(!final[w] && G.arcs[v][w].adj+min<D[w]){
D[w]=G.arcs[v][w].adj+min;
CopyQueue(Q[v],Q[w]);
EnQueue(Q[w],v);
}
}
}
// 列印出結果
cout<<"//--------------- ShortestPath -----------------//\n\n";
cout<<" 出發地->目的地\t最短距離\t詳細路徑\n\n";
for(i=0;i<G.vexnum;i++){
if(D[i]!=INFINITY){
cout<<" "<<G.vexs[v0]<<" -> "<<G.vexs[i]<<"\t\t"<<D[i]<<" \t\t";
cout<<G.vexs[v0];
while(!EmptyQueue(Q[i])){
DeQueue(Q[i],v);
cout<<" -> "<<G.vexs[v];
}
cout<<" -> "<<G.vexs[i]<<endl;
}else{
cout<<" "<<G.vexs[v0]<<" -> "<<G.vexs[i]<<"\t\tNo path!\n";

}
}
cout<<"\n//--------------- ShortestPath -----------------//\n";
}

void PrintCity(char *names,int vexnum){
int i,j;
cout<<"列表：\n\n";
for(i=0;i<vexnum;++i){
cout<<" "<<i<<"-";
for(j=0;j<4;j++){
cout<<*names;
names++;
}
cout<<" ";
}
cout<<"\n請選擇出發地點 >";
}

void main(){
MGraph G;

// 圖的結構數據
char *edges,*names;
int vexnum,arcnum,city,kind;
vexnum=6;
arcnum=10;
names="A1 A2 A3 A4 A5 A6";
edges="";

do{
PrintCity(names,vexnum);
cin>>city;
cout<<"\n\n操作：\n0－無向圖列表 1－有向圖列表\n2－無向圖矩陣 3－有向圖矩陣\n4－選擇地點 5－退出\n\n請選擇操作 >";
do{
cin>>kind;
if(kind>=0 && kind <=3){
CreateUDN(G,vexnum,arcnum,names,edges,kind%2);
switch(kind/2){
case 0:ShortestPath(G,city);
break;
case 1:PrintGraph(G);
break;
}
}
cout<<"\n\n操作：\n0－無向圖列表 1－有向圖列表\n2－無向圖矩陣 3－有向圖矩陣\n4－選擇地點 5－退出\n\n請選擇操作 >";
}
while(kind<4);
}
while(kind<5);
}

⑷ 求！最短路徑演算法 Dijkstra 用C語言編出來

Dijkstra演算法--c++源代碼--by 偉偉豬 [轉貼 2005-12-15 20:21:00 ] 發表者: 偉偉豬

/***********************************************
設G=(V,E)是一個每條邊都有非負長度的有向圖，有一個特異的頂點s稱為緣。
單源最短路徑問題，或者稱為最短路徑問題，是要確定從s到V中沒一個其他
頂點的距離，這里從頂點s到x的距離定義為從s到x的最短路徑問題。這個問題
可以用Dijkstra演算法解決。下面我給我了c++下的源代碼！ --by 偉偉豬
************************************************/
#include<iostream.h>
void main()
{
int infinity=100,j,i,n,k,t,**w,*s,*p,*d;
cout<<"input the value of n:";
cin>>n;
cout<<endl;

d=new int[n];
s=new int[n];
p=new int[n];
w=new int*[n];
for(i=0;i<n;i++) {w[i]=new int[n];}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin>>w[i][j];

for(s[0]=1,i=1;i<n;i++)
{
s[i]=0;d[i]=w[0][i];
if(d[i]<infinity) p[i]=0;
else p[i]=-1;
}

for(i=1;i<n;i++)
{
t=infinity;k=1;
for(j=1;j<n;j++)
if((!s[j])&&(d[j]<t)) {t=d[j];k=j;}
s[k]=1;//point k join the S
for (j=1;j<n;j++)
if((!s[j])&&(d[j]>d[k]+w[k][j]))
{d[j]=d[k]+w[k][j];p[j]=k;}

}
cout<<"從源點到其它頂點的最短距離依次如下：";
for(i=1;i<n;i++) cout<<d[i]<<" ";

}
/*********
頂點個數用n表示，這里給出的例子n=6
100 1 12 100 100 100
100 100 9 3 100 100
100 100 100 100 5 100
100 100 4 100 13 15
100 100 100 100 100 4
100 100 100 100 100 100
具體例子見 電子工業出版社 《演算法設計技巧與分析》148頁
************/

⑸ 嚴蔚敏的數據結構（C語言版）最短路徑演算法 代碼段：p[w]=p[v];p[w][w]=true;//p[w]=p[v]+[w]是什麼意思

二維數組P中保存的是v0到各個點的最短路徑。在v行中，值為true的列連起來，就是v0到v的最短路徑。因為v0到w點的最短路徑是v0到v的最短路徑在加上<v,w>，所以w列先復制所有的v列的值，然後在將p[w][w]=true。此時w行中所有值為true列，就是v0到w的最短路徑

⑹ 求c語言最短路徑演算法

#include <iostream>
using namespace std;

const int maxnum = 100;
const int maxint = 999999;

// 各數組都從下標1開始
int dist[maxnum]; // 表示當前點到源點的最短路徑長度
int prev[maxnum]; // 記錄當前點的前一個結點
int c[maxnum][maxnum]; // 記錄圖的兩點間路徑長度
int n, line; // 圖的結點數和路徑數

// n -- n nodes
// v -- the source node
// dist[] -- the distance from the ith node to the source node
// prev[] -- the previous node of the ith node
// c[][] -- every two nodes' distance
void Dijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum])
{
bool s[maxnum]; // 判斷是否已存入該點到S集合中
for(int i=1; i<=n; ++i)
{
dist[i] = c[v][i];
s[i] = 0; // 初始都未用過該點
if(dist[i] == maxint)
prev[i] = 0;
else
prev[i] = v;
}
dist[v] = 0;
s[v] = 1;

// 依次將未放入S集合的結點中，取dist[]最小值的結點，放入結合S中
// 一旦S包含了所有V中頂點，dist就記錄了從源點到所有其他頂點之間的最短路徑長度
// 注意是從第二個節點開始，第一個為源點
for(int i=2; i<=n; ++i)
{
int tmp = maxint;
int u = v;
// 找出當前未使用的點j的dist[j]最小值
for(int j=1; j<=n; ++j)
if((!s[j]) && dist[j]<tmp)
{
u = j; // u保存當前鄰接點中距離最小的點的號碼
tmp = dist[j];
}
s[u] = 1; // 表示u點已存入S集合中

// 更新dist
for(int j=1; j<=n; ++j)
if((!s[j]) && c[u][j]<maxint)
{
int newdist = dist[u] + c[u][j];
if(newdist < dist[j])
{
dist[j] = newdist;
prev[j] = u;
}
}
}
}

// 查找從源點v到終點u的路徑，並輸出
void searchPath(int *prev,int v, int u)
{
int que[maxnum];
int tot = 1;
que[tot] = u;
tot++;
int tmp = prev[u];
while(tmp != v)
{
que[tot] = tmp;
tot++;
tmp = prev[tmp];
}
que[tot] = v;
for(int i=tot; i>=1; --i)
if(i != 1)
cout << que[i] << " -> ";
else
cout << que[i] << endl;
}

int main()
{
freopen("input.txt", "r", stdin);
// 各數組都從下標1開始

// 輸入結點數
cin >> n;
// 輸入路徑數
cin >> line;
int p, q, len; // 輸入p, q兩點及其路徑長度

// 初始化c[][]為maxint
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
c[i][j] = maxint;

for(int i=1; i<=line; ++i)
{
cin >> p >> q >> len;
if(len < c[p][q]) // 有重邊
{
c[p][q] = len; // p指向q
c[q][p] = len; // q指向p，這樣表示無向圖
}
}

for(int i=1; i<=n; ++i)
dist[i] = maxint;
for(int i=1; i<=n; ++i)
{
for(int j=1; j<=n; ++j)
printf("%8d", c[i][j]);
printf("
");
}

Dijkstra(n, 1, dist, prev, c);

// 最短路徑長度
cout << "源點到最後一個頂點的最短路徑長度: " << dist[n] << endl;

// 路徑
cout << "源點到最後一個頂點的路徑為: ";
searchPath(prev, 1, n);
}

⑺ 求floyd最短路徑演算法，c語言代碼；

就是一個三重循環，核心代碼就這幾行
for(k=0;k<n;k++)
{

for(i=0;i<n;i++)

for(j=0;j<n;j++)

if(A[i][j]>(A[i][k]+A[k][j]))

{

A[i][j]=A[i][k]+A[k][j];

path[i][j]=k;

}
}