狄克斯特拉演算法圖解

Ⅰ 大學作業幫 一般線性規劃 求詳細解答步驟

迪傑斯特拉演算法是由荷蘭計算機科學家狄克斯特拉於1959 年提出的，因此又叫狄克斯特拉演算法。是從一個頂點到其餘各頂點的最短路徑演算法，解決的是有向圖中最短路徑問題。迪傑斯特拉演算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。

#include<stdio.h>
#include<stdlib.h>
#define max 11000000000
inta[1000][1000];
intd[1000];//d表示某特定邊距離
intp[1000];//p表示永久邊距離
inti,j,k;
intm;//m代表邊數
intn;//n代表點數
intmain()
{
scanf("%d%d",&n,&m);
intmin1;
intx,y,z;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
a[x][y]=z;
a[y][x]=z;
}
for(i=1;i<=n;i++)
d[i]=max1;
d[1]=0;
for(i=1;i<=n;i++)
{
min1=max1;
for(j=1;j<=n;j++)
if(!p[j]&&d[j]<min1)
{
min1=d[j];
k=j;
}
p[k]=j;
for(j=1;j<=n;j++)
if(a[k][j]!=0&&!p[j]&&d[j]>d[k]+a[k][j])
d[j]=d[k]+a[k][j];
}
for(i=1;i<n;i++)
printf("%d->",p[i]);
printf("%d\n",p[n]);
return0;
}

Ⅱ 狄克斯特拉的介紹

狄克斯特拉1930年5月11日生於荷蘭鹿特丹的一個知識分子家庭，在兄弟姊妹4人中排行第三。他的父親是一名化學家和發明家，曾擔任荷蘭化學會主席。他母親則是一位數學家。他成功地設計並實現了在有障礙物的兩個地點之間找出一條最短路徑的高效演算法，這個演算法被命名為「狄克斯特拉演算法」，解決了機器人學中的一個十分關鍵的問題，即運動路徑規劃問題，至今仍被廣泛應用，被認為是利用「貪心法」(greedy method)設計演算法的一個成功範例。

Ⅲ 狄克斯特拉的人生成就

狄克斯特拉1930年5月11日生於荷蘭鹿特丹的一個知識分子家庭，在兄弟姊妹4人中排行第三。他的父親是一名化學家和發明家，曾擔任荷蘭化學會主席。他母親則是一位數學家。
狄克斯特拉的少年時代是在德國法西斯佔領軍的鐵蹄下度過的。由於食物短缺，他被送到鄉下他父親的一個朋友那裡去。納粹德國投降後，1945年7月，十分虛弱的狄克斯特拉才和家人重新團聚。狄克斯特拉原打算學法律，畢業後到聯合國工作，為維護世界和平服務。但他中學畢業時，數理化成績都特別好，因此他父親說服了他，1948年進萊頓大學學習數學與物理。在學習理論物理的過程中，狄克斯特拉發現這個領域中的許多問題都需要進行大量復雜的計算，於是決定學習計算機編程。1951年，他自費赴英國參加了劍橋大學舉辦的一個程序設計培訓班，學習在EDSAC(Electronic Delay Storage Automatic Calculator，這是由另一位首屆計算機先驅獎獲得者威爾克斯主持設計與開發的世界上第一台存儲程序式電子計算機)上的編程方法，這使他成為世界上第一批程序員之一。第二年，阿姆斯特丹數學中心了解到這一情況，擬聘他為兼職程序員。狄克斯特拉開始時有些猶豫，因為世界上當時還沒有「程序員」這一職業。數學中心的計算部主任、Algol語言的設計者之一、荷蘭的計算技術先驅維京格爾藤(A．van Wijingaarden，1916—1987，因在設計Algol 68時，為解決上下文有關性這一難題而提出了一種具有很強描述能力的新的文法，稱做二級文法又稱W文法而聞名。他是1986年計算機先驅獎獲得者之一，也曾對另一位首屆計算機先驅獎獲得者N．Wirth的研究產生過影響)對他說，目前程序設計雖然還沒有成為學科，不被重視，但既然計算機已經有了，正處於開創階段，你未來就有可能使程序設計成為一個受人尊敬的學科。這段話說動了狄克斯特拉，使他接受了這個職位，而且越干越有興趣，這樣，他在第二年就結束了在萊頓大學的學業，成為數學中心全日制的工作人員，從此進入計算機領域，並且正如維京格爾藤所預言的那樣，逐漸成為該領域的知名專家，創造出了許許多多的「第一」。
1956年，他成功地設計並實現了在有障礙物的兩個地點之間找出一條最短路徑的高效演算法，這個演算法被命名為「狄克斯特拉演算法」，解決了機器人學中的一個十分關鍵的問題，即運動路徑規劃問題，至今仍被廣泛應用，被認為是利用「貪心法」(greedy method)設計演算法的一個成功範例。
1959年，在數學中心將他們原先的ARMAC計算機進行升級的過程中，狄克斯特拉設計了一種處理程序，成功地解決了「實時中斷」（real-time interrupt)問題。狄克斯特拉的博士論文就是以此為課題完成的，並在阿姆斯特丹大學通過論文答辯而獲得博士學位。
1960年8月，Algol 60文本推出剛剛半年多，狄克斯特拉和他在數學中心的同事仲納凡爾特(J．A．Zonneveld)一起就率先實現了世界上第一個Algol 60編譯器，比歐美其他各國學者實現Algol 60早一年還多。這一成就引起各國計算機學者的驚嘆，並因此奠定了狄克斯特拉作為世界一流計算機學者在科學界的地位。
1962年，狄克斯特拉離開數學中心進入位於荷蘭南部的艾恩德大學(Eindhoven Technical University)任數學教授。在這里，X8計算機的開發，設計與實現了具有多道程序運行能力統——THE Multiprogramming System。THE是艾恩德霍芬技荷蘭文Technische Hoogeschool Eindhoven的詞頭縮寫。狄克THE這個系統中所提出的一系列方法和技術奠定了計算作系統的基礎，尤其是關於多層體系結構、順序進程之間的斥機制這樣一些重要的思想和概念都是狄克斯特拉在THE中首先提出並為以後的操作系統如UNIX等所採用的。為了在單處理機的情況下確定進程(process)能否佔有處理機，狄克斯特拉將每個進程分為「就緒」(ready)、「運行」(running)和「阻塞」(blocking)三個工作狀態。由於在任一時刻最多隻有一個進程可以使用處理機，正佔用著處理機的進程稱為「運行」進程。當某進程已具備了使用處理機的條件，而當前又沒有處理機供其使用，則使該進程處於「就緒」狀態，當運行進程由於某種原因無法繼續運行下去時，就停止其佔用處理機，使之進入「阻塞』』狀態，待造成其退出運行的條件解除，再進入「就緒」狀態。而對系統中所有同時運行的進程之間所存在的相互制約的同步(synchronization，指為了避免錯誤，在一個進程訪問共享數據時，另一個進程不訪問該數據)和互斥(mutually-exclusive，指兩個進程不能同時在一個臨界區中使用同一個可重復使用的資源，諸如讀寫緩沖區)兩個關系，狄克斯特拉巧妙地利用火車運行控制系統中的「信號燈」(semaphore，或叫「信號量」)概念加以解決。所謂信號燈，實際上就是用來控制進程狀態的一個代表某一資源的存儲單元。例如，P1和P2是分別將數據送入緩沖B和從緩沖B讀出數據的兩個進程，為了防止這兩個進程並發時產生錯誤，狄克斯特拉設計了一種同步機制叫PV操作」，P操作和V操作是執行時不被打斷的兩個操作系統原語。執行P操作P(S)時信號量S的值減1，若結果不為負則P(S)執行完畢，否則執行P操作的進程暫停以等待釋放。執行V操作V(S)時，S的值加1，若結果不大於0則釋放一個因執行P(S)而等待的進程。對P1和凹可定義兩個信號量S1和S2，初值分別為1和0。進程P1在向緩沖B送人數據前執行P操作P(S1)，在送人數據後執行V操作V(S2)。進程P2在從緩沖B讀取數據前先執行P操作P(S2)，在讀出數據後執行V操作V(S1)。當P1往緩沖B送入一數據後信號量S1之值變為0，在該數據讀出後S1之值才又變為1，因此在前驅數未讀出前後續數不會送入，從而保證了P1和P2之間的同步。我國讀者常常不明白這一同步機制為什麼稱做PV操作，原來這是狄克斯特拉用荷蘭文定義的，因為在荷蘭文中，通過叫passeren，釋放叫，VRIJGEVEN，PV操作因此得名。這是在計算機術語中不用英語表達的極少數的例子之一。

Ⅳ dijkstra演算法是什麼

Dijkstra演算法是由荷蘭計算機科學家狄克斯特拉（Dijkstra）於1959年提出的，因此又叫狄克斯特拉演算法。是從一個頂點到其餘各頂點的最短路徑演算法，解決的是有向圖中最短路徑問題。

其基本原理是：每次新擴展一個距離最短的點，更新與其相鄰的點的距離。當所有邊權都為正時，由於不會存在一個距離更短的沒擴展過的點，所以這個點的距離永遠不會再被改變，因而保證了演算法的正確性。

不過根據這個原理，用Dijkstra求最短路的圖不能有負權邊，因為擴展到負權邊的時候會產生更短的距離，有可能就破壞了已經更新的點距離不會改變的性質。

舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離。Dijkstra演算法可以用來找到兩個城市之間的最短路徑。

Dijkstra演算法的輸入包含了一個有權重的有向圖G，以及G中的一個來源頂點S。我們以V表示G中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。（u,v)表示從頂點u到v有路徑相連。我們以E所有邊的集合，而邊的權重則由權重函數w: E→[0,∞］定義。

因此，w(u,v)就是從頂點u到頂點v的非負花費值（cost)。邊的花費可以想像成兩個頂點之間的距離。任兩點間路徑的花費值，就是該路徑上所有邊的花費值總和。

已知有V中有頂點s及t，Dijkstra演算法可以找到s到t的最低花費路徑（i.e.最短路徑）。這個演算法也可以在一個圖中，找到從一個頂點s到任何其他頂點的最短路徑。

Ⅳ c++數據結構的圖的應用，求圖的最小生成樹和最短路徑有什麼不同，或者是普里姆演算法和狄克斯特拉演算法有

不知道你的手頭有沒有一本經典的書籍叫做《大話數據結構》，如果解釋的話，似乎還真不容易解釋，請找一下這本書的電子版，查閱一下相關章節更清楚，祝你好運。
http://yunpan.cn/cwbziapG5St3w 訪問密碼 91ac

Ⅵ 狄克斯特拉的簡介

埃德斯加·狄克斯特拉
——最先察覺「goto有害」的計算機科學大師
首屆計算機先驅獎獲得者中有一位荷蘭的計算機科學家埃德斯加·狄克斯特拉(Edsgar Wybe Dijkstra)。狄克斯特拉因最早指出「goto是有害的」以及首創結構化程序設計而聞名於世。事實上，他對計算機科學的貢獻並不僅僅限於程序設計技術。在演算法和演算法理論、編譯器、操作系統諸多方面，狄克斯特拉都有許多創造，作出了傑出貢獻。1983年，ACM為紀念Communications of ACM創刊25周年，評選出從1958—1982年的四分之一個世紀中在該雜志上發表的25篇有里程碑意義的論文，每年一篇，狄克斯特拉一人就有兩篇入選，是僅有的這樣的兩位學者之一(另一位是英國學者C．A．R．Hoare，也是計算機先驅獎獲得者)。

Ⅶ 各位快來幫幫忙 關於Dijkstra演算法的

樓主說的對，說明你在研究這個問題很好。最短路徑就是是最小生成樹的n-1條邊！

Ⅷ OSPF的演算法是什麼

我們知道，對於有向連通圖，以任意一個節點為起點，利用最短路徑演算法可以計算出到其他節點的最短路徑。那麼，對於能抽象成有向連通圖的網路拓撲來說，也可以利用最短路徑演算法先計算出以任意一台路由器為起點，到達其他路由器的最短路徑，然後根據各路由器的網路連接情況可以得到到各個網路的路由路徑。
OSPF中用到的Dijkstra演算法和RIP中用到的距離向量演算法一樣，都是相當經典的最短路徑演算法。本文將對Dijkstra演算法及OSPF協議對Dijkstra演算法的使用進行介紹。
1 Dijkstra演算法介紹
在數學上，以某個節點為起點，計算到其他節點的最短路徑的演算法，稱為「單源最短路徑」 演算法。求「單源最短路徑」的問題在數學上可以精確描述如下：
「單源最短路徑」 問題：已知一個有n個節點(V0..n)構成的有向連通圖G=(V，E)，以及圖中邊的權函數C (E)，其中V代表節點集合，E表示所有邊的集合，並假設所有權非負，求由G中指定節點V0到其他各個節點的最短路徑。
Dijkstra演算法是很經典的求解上述問題的演算法，其基本想法是設計一種最短路徑樹的構造方法，按非降次序逐條構造從V0到各個節點的最短路徑，第一步找到和V0相距最短的節點以及到這個節點的路徑，第二步找到和V0相距次短的節點以及到這個節點的路徑，如此反復，最後找到V0到所有節點的最短路徑，構造出整棵最短路徑樹。
對上述構造方法的一個直觀考慮是：和V0相距最短的節點應該在和V0直接相鄰的節點中，和V0相距次短的節點要麼在和V0直接相鄰的節點中，要麼在和這些相鄰節點相鄰的節點中，如此逐步擴散考慮，應該就可以找到和V0相距最短、次短、…….第n短的節點以及對應的路徑，而且因為是連通圖，最後肯定所有節點都能全部考慮到，也就能完成整棵最短路徑樹的構造。
事實上，上述直觀考慮是對的，Dijkstra演算法是對上述過程的一個提煉和優化：和V0相距最短的節點是和V0直接相連的節點沒錯;相距次短的節點范圍可以縮小為，和V0直接相鄰的節點，加上跟剛選中的最短節點直接相鄰的節點;相距第三短的節點的范圍可以類推得到，即在上一步考察的節點的基礎上，加上和次短節點直接相鄰的節點。如此逐步構造，可以按非降次序找到到所有節點的最短路徑。
為了從數學上精確描述上述構造過程，引入了集合的概念對節點和路徑進行分類。
我們把節點分成兩個集合：
A：已經選入最短路徑樹的節點的集合。
B：剩餘的其他節點的集合。
對於路徑，我們分成三個集合：
(1)已經選入最短路徑樹的路徑的集合
(2)候選路徑集合：下一條加入最短路徑樹的路徑將從這個集合中選入
(3)剩餘的其他路徑的集合(被廢棄的路徑或者還未考慮的路徑)
為了更好的理解，有必要對這里的路徑定義進行一下強調：路徑是指以V0為起點，其他節點為終點的由一條或多條邊組成的一個有序集。邊，可以理解為路徑中的一段，只有到和V0直接相鄰的節點的路徑才直接對應一條邊。從V0到所有節點，都可能存在一條或多條路徑，非最短路徑在計算過程中將會被廢棄，放入集合III。
從前面的描述中可以明顯看出，Dijkstra演算法是一個遞歸構造過程，因為任何遞歸都必須有明確的初始狀態，所以我們有必要先得到上述Dijkstra演算法中定義的集合的初始值：
l 以V0為起點計算最短路徑的話，初始狀態時顯然有且只有V0在集合A中，所以集合A的初始值為V0。集合B的初始值為剩餘節點。
l 前面提到過，下一個加入集合A的節點，一定是和V0直接有邊相連的節點，因此，加入最短路徑樹的第一條路徑也必然在這些和V0直接相連的邊所代表的路徑中產生，所以集合II的初始值就是和V0直接相連的邊構成的路徑。另外，初始狀態最短路徑樹為空，所以集合I的初始值為空。集合I、II明確了的話，集合III自然明確。
下面我們開始展開遞歸構造最短路徑樹的過程：
l 第一步：從集合II中選擇一條最短的路徑，放入最短路徑樹，相應的，這條路徑的終點對應的節點(這里記為X)應該從集合B移入集合A。
l 第二步：考察所有從X出發的邊的終點，考慮其中不屬於集合A的節點，這里記為Y，計算從V0出發經X到達Y的路徑值，計算方法為：最短路徑樹中V0到節點X的路徑值加上(X，Y)這條邊的值。為了描述方便，我們把從V0出發經X到達Y的路徑記為(V0X)Y。接著考察集合II中的候選路徑，如果其中沒有到節點Y的路徑，則直接把路徑(V0X)Y作為候選路徑加入集合II;如果集合II中已經有到節點Y的路徑，則進行比較，如果這條路徑值小於或等於路徑 (V0X)Y的路徑值，那麼路徑(V0X)Y作為被廢棄的路徑放入集合III，否則原集合II中到Y的路徑被廢棄放入集合II，(V0X)Y作為候選路徑放入集合II。對於Y節點有多個的情況，按第二步的方法一個一個的計算和比較。
l 重復第一步和第二步，直到集合II和集合B為空。

Ⅸ 關於圖的最短路徑問題

醫院選址
1.
代碼如下

#include <iostream>
using namespace std;
#define MAXV 50
#define INF 32767
typedef int InfoType;
//鄰接矩陣存儲方法
typedef struct
{
int no;
InfoType info;
} VertexType;
typedef struct
{
int edges[MAXV][MAXV];
int n,e;
VertexType vexs[MAXV];
} MGraph;
//狄克斯特拉演算法
void Ppath(int path[],int i,int v)
{
int k;
k=path[i];
if(k==v) return;
Ppath(path,k,v);
cout<<k;
}
int biaoji1=0,biaoji2=0;
void Dispath(int dist[],int path[],int s[],int n,int v)
{
int i;
for(i=0;i<n;i++)
{
if(i==v) continue;
if(s[i]==1)
{
cout<<"從"<<v<<"到"<<i<<"的最短路徑為："<<dist[i]<<" ";
cout<<v;
Ppath(path,i,v);
cout<<i<<endl;
if(biaoji1!=5)
{biaoji2+=dist[i];biaoji1++;}
else
{
cout<<"和為："<<" "<<biaoji2;
biaoji1=0;biaoji2=0;
}
}
else
cout<<"從"<<v<<"到"<<i<<"不存在的路徑"<<endl;
}
}
void Dijkstra(MGraph g,int v)
{
int dist[MAXV],path[MAXV];
int s[MAXV];
int mindis,i,j,u;
for(i=0;i<g.n;i++)
{
dist[i]=g.edges[v][i];
s[i]=0;
if(g.edges[v][i]<INF) path[i]=v;
else path[i]=-1;
}
s[v]=1;path[v]=0;
for(i=0;i<g.n;i++)
{
mindis=INF;
for(j=0;j<g.n;j++)
{
if(s[j]==0&&dist[j]<mindis)
{
u=j;
mindis=dist[j];
}
}
s[u]=1;
for(j=0;j<g.n;j++)
{
if(s[j]==0)
{
if(g.edges[u][j]<INF&&dist[u]+g.edges[u][j]<dist[j])
{
dist[j]=dist[u]+g.edges[u][j];
path[j]=u;
}
}
}
}
Dispath(dist,path,s,g.n,v);
}
//弗洛伊德演算法
void Ppath1(int path[][MAXV],int i,int j)
{
int k;
k=path[i][j];
if(k==-1) return;
Ppath1(path,i,k);
cout<<k;
Ppath1(path,k,j);
}
void Dispath1(int A[][MAXV],int path[][MAXV],int n)
{
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==j) continue;
if(A[i][j]==INF)
{
if(i!=j)
cout<<"從"<<i<<"到"<<j<<"不存在路徑"<<endl;
}
else
{
cout<<"從"<<i<<"到"<<j<<"的最短路徑長度為:"<<A[i][j]<<" ";
cout<<i;
Ppath1(path,i,j);
cout<<j<<endl;
}
}
}
}
void Floyd(MGraph g)
{
int A[MAXV][MAXV],path[MAXV][MAXV];
int i,j,k;
for(i=0;i<g.n;i++)
{
for(j=0;j<g.n;j++)
{
A[i][j]=g.edges[i][j];
path[i][j]=-1;
}
}
for(k=0;k<g.n;k++)
{
for(i=0;i<g.n;i++)
{
for(j=0;j<g.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;
}
}
}
}
Dispath1(A,path,g.n);
}

//主函數
int main()
{
int i,j,n;
MGraph g;
cout<<"請輸入帶權有向圖的頂點個數：";//6
while(scanf("%d",&n)!=EOF/*cin>>n,n!=EOF*/)
{
cout<<"請輸入帶權有向圖的鄰接矩陣："<<endl;
/*
0 5 32767 7 32767 32767
32767 0 4 32767 32767 32767
8 32767 0 32767 32767 9
32767 32767 5 0 32767 6
32767 32767 32767 5 0 32767
3 32767 32767 32767 1 0
*/

for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
//scanf("%d",&g.edges[i][j]);
cin>>g.edges[i][j];
}
}
g.n=n;
cout<<"採用狄克斯特拉演算法得到的最短路徑為："<<endl;
for(i=0;i<n;i++) Dijkstra(g,i);
cout<<endl;
cout<<"採用弗洛伊德演算法得到的最短路徑為："<<endl;
Floyd(g);
cout<<endl;
cout<<"請輸入帶權無向圖的頂點個數：";
}
return 0;
}

2.代碼如下

#include <iostream>
using namespace std;
int INFTY=32767;
template<class T>
class Graph
{
public:
virtual void Insert(int u,int v,T& w)=0;
virtual void Remove(int u,int v)=0;
virtual bool Exist(int u,int v)=0;
virtual int Vertices()const {return n;}
protected:
int n,e;

};
template <class T>
class MGraph:public Graph<T>//鄰接矩陣存儲圖
{
public:
MGraph();
~MGraph();
void Build_Graph();
void Insert(int u,int v,T& w);
void Remove(int u,int v);
bool Exist(int u,int v);
void Floyd(T**&d,int**&path);
int num;
protected:
T**a;
T noEdge;
};
template <class T>
void MGraph<T>::Build_Graph()//建圖
{
cout<<"請輸入頂點的個數："<<endl;
int C_num;
cin>>C_num;
num=n=C_num;e=0;noEdge=INFTY;
a=new T*[n];
for(int k=0;k<n;k++){
a[k]=new T [n];
for(int j=0;j<n;j++)a[k][j]=noEdge;
a[k][k]=0;
}
cout<<"建立村莊編號為1--"<<C_num<<"的圖"<<endl;
for(int i=0;i!=C_num;i++)
for(int j=i+1;j!=C_num;j++)
{
int w;
cout<<"請輸入村莊"<<i+1<<"與村莊"<<j+1<<"之間的權值：";
cin>>w;
Insert(i,j,w); //向圖中添加權值為W的邊
cout<<i<<"--->"<<j<<":"<<a[i][j]<<endl;
}
cout<<"*********************************************************************"<<endl;
cout<<"已建立村莊編號為1--"<<C_num<<"的圖:"<<endl;
cout<<"**********************************"<<endl;
cout<<" \t\t";
for(int b=1;b<=C_num;b++){

cout<<b<<"\t";
}
cout<<endl;
}

template <class T>
MGraph<T>::MGraph()
{
Build_Graph();
}

template <class T>
MGraph<T>::~MGraph()
{
for(int i=0;i<n;i++)delete[]a[i];
delete[]a;
}

template <class T>
bool MGraph<T>::Exist(int u,int v)
{
if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]==noEdge) return false;
return true;
}
template <class T>
void MGraph<T>::Insert(int u,int v,T &w)
{
a[u][v]=w;a[v][u]=w;e++;
}
template <class T>
void MGraph<T>::Remove(int u,int v)
{
a[u][v]=noEdge;e--;
}

template <class T>
void MGraph<T>::Floyd(T**&d,int**&path)//所有頂點之間的最短路徑
{
int i,j,k;
d=new T*[n];path=new int*[n];
for(i=0;i<n;i++){
d[i]=new T[n];path[i]=new int[n];
for(j=0;j<n;j++){
d[i][j]=a[i][j];
if(i!=j&& a[i][j]<INFTY)path[i][j]=i;
else path[i][j]=-1;
}
}
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(d[i][k]+d[k][j]<a[i][j]){
d[i][j]=d[i][k]+d[k][j];
path[i][j]=path[k][j];
}
}
int main()
{
MGraph<int> Hospital;
int **d,**path;
int i,j,n;
n=Hospital.num;
Hospital.Floyd(d,path);
int *sum=new int[n];
cout<<endl;
for(i=0;i!=n;i++)//輸出矩陣
{
cout<<i+1<<"\t\t";
sum[i]=0;
for(j=0;j!=n;j++)
{
sum[i]+=d[i][j];
cout<<d[i][j]<<"\t";
}
cout<<endl;
}
cout<<"*********************************************************************"<<endl;
int min=0;
for(i=0;i!=n;i++)
{
cout<<i+1<<"村莊："<<sum[i]<<endl;
if(sum[min]>sum[i])//判斷最短路徑
min=i;
}
cout<<"醫院應在編號為"<<min+1<<"的村莊"<<endl;
for(i=0;i<n;i++)
{
delete[]d[i];
delete[]path[i];
}
delete[]d;
delete[]path;
return 0;
}

Ⅹ 狄克斯特拉演算法的path是怎麼算出來的

Dijkstra演算法（狄克斯特拉演算法） Dijkstra演算法是由荷蘭計算機科學家 狄克斯特拉 （ Dijk stra ）於1959 年提出的，因此又叫狄克斯特拉演算法。 是從一個頂點到其餘各頂點的最短路徑演算法， 解決的是有向圖中最短路徑問題。

程序如下，稍加改動即可。
帶權有向圖的最短路徑的求解
//帶權有向圖的最短路徑的求解
#include <stdio.h>
#include <stdlib.h>
#define MAXV 50
#define INF 32767
typedef int InfoType;
//鄰接矩陣存儲方法
typedef struct
{
int no;
InfoType info;
} VertexType;
typedef struct
{
int edges[MAXV][MAXV];
int n,e;
VertexType vexs[MAXV];
} MGraph;
//狄克斯特拉演算法
void Ppath(int path[],int i,int v)
{