最短路徑演算法-九游会j9娱乐平台
㈠ 圖論中常見的最短路徑演算法有幾種都是什麼
主要是有三種、、
第一種是最直接的貪心dijkstra演算法、、可以利用堆數據結構進行優化、、缺點就是不能求有負權的最短路與判斷負環、、
第二種是bellman-ford演算法、、根據鬆弛操作的性質是可以來判斷負環的、、時間復雜度是o(nm)的、、
第三種是spfa演算法、、把他單獨拿出來作為一種演算法並不是非常好的、、他的實質應該是上面的bellman-ford演算法的隊列優化時間復雜度更低、o(ke)、k的值約等於2、、
㈡ 求一個最短路徑的演算法
以前看到過，貼給你
private function orderxy(x() as double, y() as double)
dim i, j, k, m, n, num, temp as double
dim newx() as double
dim newy() as double
dim smin as double '定義最短總距離
if ubound(x()) <> ubound(y()) then msgbox "坐標錯誤": exit function '防止數據錯誤
n = ubound(x())
redim p(n) as long
p(0) = 0: num = 1
for i = 1 to n
p(i) = i 'p()數組依次存儲從0到n共n 1個數
num = num * i '計算num，num表示的是n個坐標（除x(0),y(0)以外)共有n！種排列
next
redim stance(num - 1) as double '定義數組存儲每種連接方法的總距離
redim newx(n)
redim newy(n)
for i = 0 to n - 1 'stance（0）是按照原坐標順序依次連接的總距離
stance(0) = stance(0) sqr((y(i 1) - y(i)) * (y(i 1) - y(i)) (x(i 1) - x(i)) * (x(i 1) - x(i)))
next
smin = stance(0)
for k = 0 to n
newx(k) = x(k)
newy(k) = y(k)
next
i = n - 1
'下面對p()數組的n個數（除0以外）進行排列，每產生一種排列方式，坐標數組的數據就對應交換，並計算這一路徑的總距離
do while i > 0
if p(i) < p(i 1) then
for j = n to i 1 step -1 '從排列右端開始
if p(i) <= p(j) then exit for '找出遞減子序列
next
temp = p(i): p(i) = p(j): p(j) = temp '將遞減子序列前的數字與序列中比它大的第一個數交換
temp = x(i): x(i) = x(j): x(j) = temp '與之對應的x y也交換
temp = y(i): y(i) = y(j): y(j) = temp
for j = n to 1 step -1 '將這部分排列倒轉
i = i 1
if i >= j then exit for
temp = p(i): p(i) = p(j): p(j) = temp
temp = x(i): x(i) = x(j): x(j) = temp
temp = y(i): y(i) = y(j): y(j) = temp
next
m = m 1
for k = 0 to n - 1
stance(m) = stance(m) sqr((y(k 1) - y(k)) * (y(k 1) - y(k)) (x(k 1) - x(k)) * (x(k 1) - x(k)))
next
if stance(m) <= smin then
smin = stance(m)
for k = 0 to n
newx(k) = x(k): newy(k) = y(k)
next
end if
i = n
end if
i = i - 1
loop
for k = 0 to n
x(k) = newx(k): y(k) = newy(k)
next '此時的x（） y（） 就按照最短路徑排列
end function
㈢ "最短路徑優先演算法"的優缺點
這個演算法一般出現在網路中，用於路由器的路由定址，我也只了解這方面的優缺點。如果不對，lz就別看了。
所謂最短路徑，實際上說的是跳數。比如從一條路走會經過三個路由器，而從另一條路走，會經過兩個路由器，那麼此演算法會判斷2跳比3跳要短，但具體每一跳會花多長時間，經過多長路程，它不會考慮的。所以不一定演算法的最短路徑就是真實的最短。因為很多因素演算法沒有考慮，比如通信質量，網線長度……
c語言我只看過一個模擬現實的例子，大概是說公車走什麼路線長度最短，那個演算法考慮的是路線的長短，而不是跳數，優點當然就是路線的絕對最短，缺點就是沒考慮到其他現實因素，比如是否堵車（相當於網路通信質量）之類。
總之不管什麼演算法，考慮到的因素就是它的優點，反過來說，缺點往往就是演算法忽略的因素。
補充一下，如果說的不是演算法本身的優劣，而是細節的實現方面，那就是從時間復雜度和空間復雜度兩個方面去考慮了，希望對lz有用。
㈣ 最短路徑法如何計算
最短路徑演算法有三種，floyd，dijkstra，bellman_ford。其中，floyd適合用於計算每兩點間的路徑，dijkstra適合稀疏圖，bellman則適合稠密圖中的已知起點終點，計算最短路徑的問題。時間復雜度，floyd演算法為n立方，dijk為n平方，bellman為n平方，其中n是點數。dijk可用堆維護，時間復雜度可減至nlogn，而bellman可用隊列維護，此方法於1994年被國人提出，命名比較土鱉叫spfa(shortest path faster algorithm。。。)。至於如何計算，有了名字，搜一下就ok。
㈤ 關於時間依賴的最短路徑演算法
dijkstra 最短路徑演算法的一種高效率實現*
隨著計算機的普及以及地理信息科學的發展，gis因其強大的功能得到日益廣泛和深入的應用。網路分析作為gis最主要的功能之一，在電子導航、交通旅遊、城市規劃以及電力、通訊等各種管網、管線的布局設計中發揮了重要的作用，而網路分析中最基本最關鍵的問題是最短路徑問題。最短路徑不僅僅指一般地理意義上的距離最短，還可以引申到其他的度量，如時間、費用、線路容量等。相應地，最短路徑問題就成為最快路徑問題、最低費用問題等。由於最短路徑問題在實際中常用於汽車導航系統以及各種應急系統等（如110報警、119火警以及醫療救護系統），這些系統一般要求計算出到出事地點的最佳路線的時間應該在1 s～3 s內，在行車過程中還需要實時計算出車輛前方的行駛路線，這就決定了最短路徑問題的實現應該是高效率的。其實,無論是距離最短、時間最快還是費用最低，它們的核心演算法都是最短路徑演算法。經典的最短路徑演算法——dijkstra演算法是目前多數系統解決最短路徑問題採用的理論基礎，只是不同系統對dijkstra演算法採用了不同的實現方法。
據統計，目前提出的此類最短路徑的演算法大約有17種。f.benjamin zhan等人對其中的15種進行了測試，結果顯示有3種效果比較好，它們分別是：tqq（graph growth with two queues）、dka (the dijkstra's algorithm implemented with approximate buckets) 以及 dkd (the dijkstra�s algorithm implemented with double buckets )，這些演算法的具體內容可以參見文獻〔1〕。其中tqq演算法的基礎是圖增長理論，較適合於計算單源點到其他所有點間的最短距離；後兩種演算法則是基於dijkstra的演算法，更適合於計算兩點間的最短路徑問題〔1〕。總體來說，這些演算法採用的數據結構及其實現方法由於受到當時計算機硬體發展水平的限制，將空間存儲問題放到了一個很重要的位置，以犧牲適當的時間效率來換取空間節省。目前，空間存儲問題已不是要考慮的主要問題，因此有必要對已有的演算法重新進行考慮並進行改進，可以用空間換時間來提高最短路徑演算法的效率。
1 經典dijkstra演算法的主要思想
dijkstra演算法的基本思路是：假設每個點都有一對標號 (dj, pj)，其中dj是從起源點s到點j的最短路徑的長度 (從頂點到其本身的最短路徑是零路(沒有弧的路)，其長度等於零)；pj則是從s到j的最短路徑中j點的前一點。求解從起源點s到點j的最短路徑演算法的基本過程如下：
1) 初始化。起源點設置為：① ds=0, ps為空;② 所有其他點: di=∞, pi= ;③ 標記起源點s，記k=s,其他所有點設為未標記的。
2) 檢驗從所有已標記的點k到其直接連接的未標記的點j的距離，並設置：
dj=min〔dj, dk lkj〕
式中，lkj是從點k到j的直接連接距離。
3) 選取下一個點。從所有未標記的結點中，選取dj 中最小的一個i：
di=min〔dj, 所有未標記的點j〕
點i就被選為最短路徑中的一點，並設為已標記的。
4) 找到點i的前一點。從已標記的點中找到直接連接到點i的點j*，作為前一點,設置：
i=j*
5) 標記點i。如果所有點已標記，則演算法完全推出，否則，記k=i，轉到2) 再繼續。
2 已有的dijkstra演算法的實現
從上面可以看出，在按標記法實現dijkstra演算法的過程中，核心步驟就是從未標記的點中選擇一個權值最小的弧段，即上面所述演算法的2)～5)步。這是一個循環比較的過程，如果不採用任何技巧，未標記點將以無序的形式存放在一個鏈表或數組中。那麼要選擇一個權值最小的弧段就必須把所有的點都掃描一遍，在大數據量的情況下，這無疑是一個制約計算速度的瓶頸。要解決這個問題，最有效的做法就是將這些要掃描的點按其所在邊的權值進行順序排列，這樣每循環一次即可取到符合條件的點，可大大提高演算法的執行效率。另外，gis中的數據 (如道路、管網、線路等)要進行最短路徑的計算，就必須首先將其按結點和邊的關系抽象為圖的結構，這在gis中稱為構建網路的拓撲關系 (由於這里的計算與面無關，所以拓撲關系中只記錄了線與結點的關系而無線與面的關系，是不完備的拓撲關系)。如果用一個矩陣來表示這個網路，不但所需空間巨大，而且效率會很低。下面主要就如何用一個簡潔高效的結構表示網的拓撲關系以及快速搜索技術的實現進行討論。
網路在數學和計算機領域中被抽象為圖，所以其基礎是圖的存儲表示。一般而言，無向圖可以用鄰接矩陣和鄰接多重表來表示，而有向圖則可以用鄰接表和十字鏈表〔4〕 表示，其優缺點的比較見表 1。
表 1 幾種圖的存儲結構的比較
tab. 1 the comparsion of several graph for storing structures
名 稱 實現方法 優 點 缺 點 時間復雜度
鄰接矩陣 二維數組 1. 易判斷兩點間的關系 佔用空間大 o(n2 m*n)
2. 容易求得頂點的度
鄰接表 鏈表 1. 節省空間 1. 不易判斷兩點間的關系 o(n m)或o(n*m)
2. 易得到頂點的出度 2. 不易得到頂點的入度
十字鏈表 鏈表 1. 空間要求較小 結構較復雜 同鄰接表
2.易求得頂點的出度和入度
鄰接多重表 鏈表 1. 節省空間 結構較復雜 同鄰接表
2. 易判斷兩點間的關系
目前,對於演算法中快速搜索技術的實現，主要有桶結構法、隊列法以及堆棧實現法。tqq、dka 以及 dkd 在這方面是比較典型的代表。tqq雖然是基於圖增長理論的，但是快速搜索技術同樣是其演算法實現的關鍵，它用兩個fifo的隊列實現了一個雙端隊列結構來支持搜索過程〔1〕。
dka和dkd是採用如圖 1 所示的桶結構來支持這個運算，其演算法的命名也來源於此。在dka演算法中，第i個桶內裝有權值落在 〔b*i, (i 1)*b) 范圍內的可供掃描的點，其中b是視網路中邊的權值分布情況而定的一個常數。每一個桶用隊列來維護，這樣每個點有可能被多次掃描，但最多次數不會超過b次。最壞情況下，dka的時間復雜度將會是o(m*b n(b c/b))，其中，c為圖中邊的最大權值。dkd將點按權值的范圍大小分裝在兩個級別的桶內，高級別的桶保存權值較大的點，相應的權值較小的點都放在低級別的桶內，每次掃描都只針對低級別桶中的點。當然隨著點的插入和刪除，兩個桶內的點是需要動態調整的。在dka演算法中，給每個桶一定的范圍以及dkd中使用雙桶，在一定程度上都是以空間換時間的做法，需要改進。
圖 1 一個桶結構的示例
fig. 1 an example of the bucket data structure
3 本文提出的dijkstra演算法實現
3.1 網路拓撲關系的建立
上面介紹的各種圖的存儲結構考慮了圖在理論上的各種特徵，如有向、無向、帶權、出度、入度等。而gis中的網路一般為各種道路、管網、管線等，這些網路在具有圖理論中的基本特徵的同時，更具有自己在實際中的一些特點。首先，在gis中大多數網路都是有向帶權圖，如道路有單雙向問題，電流、水流都有方向（如果是無向圖也可歸為有向圖的特例），且不同的方向可能有不同的權值。更重要的一點是，根據最短路徑演算法的特性可以知道，頂點的出度是個重要指標，但是其入度在演算法里則不必考慮。綜合以上4種存儲結構的優缺點， 筆者採用了兩個數組來存儲網路圖，一個用來存儲和弧段相關的數據（net-arc list），另一個則存儲和頂點相關的數據（net-node index）。net-arc list用一個數組維護並且以以弧段起點的點號來順序排列，同一起點的弧段可以任意排序。這個數組類似於鄰接矩陣的壓縮存儲方式，其內容則具有鄰接多重表的特點，即一條邊以兩頂點表示。net-node index則相當於一個記錄了頂點出度的索引表，通過它可以很容易地得到此頂點的出度以及與它相連的第一條弧段在弧段數組中的位置。此外，屬性數據作為gis不可少的一部分也是必須記錄的。這樣，計算最佳路徑所需的網路信息已經完備了。在頂點已編號的情況下，建立net-arc list和net-node index兩個表以及對net-arc list的排序，其時間復雜度共為o(2n lgn)，否則為o(m 2n lgn)。這個結構所需的空間也是必要條件下最小的，記錄了m個頂點以及n條邊的相關信息，與鄰接多重表是相同的。圖 2 是採用這個結構的示意圖。
3.2 快速搜索技術的實現
無論何種演算法，一個基本思想都是將點按權值的大小順序排列，以節省操作時間。前面已經提到過，這兩個演算法都是以時間換空間的演算法，所以在這里有必要討論存儲空間問題 (這部分空間的大小依賴於點的個數及其出度)。根據圖中頂點和邊的個數可以求出頂點的平均出度e=m/n（m為邊數，n為頂點數），這個數值代表了圖的連通程度，一般在gis的網路圖中，e∈〔2,5〕。這樣,如果當前永久標記的點為t個，那麼，下一步需掃描點的個數就約為t～4t個。如果採用鏈表結構，按實際應用中的網路規模大小，所需的總存儲空間一般不會超過100 k。所以完全沒有必要採用以時間換空間的做法，相反以空間換時間的做法是完全可行的。在實現這部分時，筆者採用了一個fifo隊列，相應的操作主要是插入、排序和刪除，插入和刪除的時間復雜度都是o(1)，所以關鍵問題在於選擇一個合適的排序演算法。一般可供選擇的排序演算法有快速排序、堆排序以及歸並排序等，其實現的平均時間都為o(nlgn)。經過比較實驗，筆者選擇了快速排序法。另外，visual c 提供的run-time庫也提供了現成的快速排序的函數qsort( )可供使用。
圖 2 基於最佳路徑計算的網路拓撲表示
fig. 2 the presentation of the network topology
used for computing the shortest path
按照以上思路，筆者用visual c 實現了吉奧之星（geostar）中的最佳路徑模塊。以北京的街道為數據（共6 313個結點，9 214條弧段(雙向)），在主頻為133、硬碟為1 g、內存為32 m的機器上，計算一條貫穿全城、長為155.06 km的線路，約需1 s～2 s。如圖 3所示。
圖 3 geostar中最佳路徑實現示意圖
ps:圖片沒有辦法貼上去.
你可以參考《演算法導論》第二版
㈥ 最短路徑演算法 c語言
#include
#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 用c語言編出來
#include"iostream.h"
#include"stdlib.h"
#define maxpoint 3//定義最大的頂點數目
#define limit 32767 //設置沒有路徑的權代替無窮大
struct record{ //沒個頂點的數據結構設置為一個數組隊列
int number; //頂點號
int flag; //標志是否從隊列中被選過如果為1表示選過為0表示未選
int allpath; //從源點到這個點的當前最短距離（權最小）
}path[maxpoint 1];
int cost[maxpoint 1][maxpoint 1]; //用來表示圖的鄰接矩陣
void main()
{int i,j,temp,front=1,rear=maxpoint,n,minnumber;
//temp表示在數組隊列中的當前下標 front表示隊列首 rear表示隊列尾
//n 表示待輸入的源點號碼 minnumber 表示選中的點的號碼
int min=32768; //設置一個初始值
for(i=1;i<=maxpoint;i )
for(j=1;j<=maxpoint;j )
{cout<<"請輸入從第"<
}
//cout<<"請輸入源點號"<
for(n=maxpoint;n>=1;n--)//把每一個點輪流地都設置為起點，可以求出任意一對頂點之間的最短路徑
{ for(i=front;i<=rear;i ) //初始化每個點的信息
{if(i==n)
path[i].allpath=0;
else
path[i].allpath=limit;
path[i].flag=0;
path[i].number=i;
}
while(rear>=1) //控制循環次數
{for(temp=front;temp<=maxpoint;temp )
{ if(path[temp].allpath
{ minnumber=path[temp].number;
min=path[temp].allpath ;
}
}
min=32768;
path[minnumber].flag=1;//把選中的點的標志變數置1表示已經被選過避免選中
for(i=1;i<=maxpoint;i )//進行類似廣度優先搜索，更新最短路徑
{if((i!=minnumber)&&(path[minnumber].allpath cost[minnumber][i]
}
rear--;//次數減1
}
rear=maxpoint; //恢復數組以便於下一點的循環
for(j=1;j<=maxpoint;j )
{ cout<<"第"<
}
}
//這個程序可以求出任意一對頂點之間的最短路徑，不過這種演算法效率還不是很高，還有其他演算法待續
㈧ 最短路徑演算法作用
可以實現距離最短以及時間最短，從而為你節約行程的成本
㈨ 計算機網路的最短路徑演算法有哪些對應哪些協議
用於解決最短路徑問題的演算法被稱做「最短路徑演算法」，有時被簡稱作「路徑演算法」。最常用的路徑演算法有：
dijkstra演算法、a*演算法、spfa演算法、bellman-ford演算法和floyd-warshall演算法，本文主要介紹其中的三種。
最短路徑問題是圖論研究中的一個經典演算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。
演算法具體的形式包括：
確定起點的最短路徑問題：即已知起始結點，求最短路徑的問題。
確定終點的最短路徑問題：與確定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同於把所有路徑方向反轉的確定起點的問題。
確定起點終點的最短路徑問題：即已知起點和終點，求兩結點之間的最短路徑。
全局最短路徑問題：求圖中所有的最短路徑。
floyd
求多源、無負權邊的最短路。用矩陣記錄圖。時效性較差，時間復雜度o(v^3)。
floyd-warshall演算法（floyd-warshall algorithm）是解決任意兩點間的最短路徑的一種演算法，可以正確處理有向圖或負權的最短路徑問題。
floyd-warshall演算法的時間復雜度為o(n^3)，空間復雜度為o(n^2)。
floyd-warshall的原理是動態規劃：
設di,j,k為從i到j的只以(1..k)集合中的節點為中間節點的最短路徑的長度。
若最短路徑經過點k，則di,j,k = di,k,k-1 dk,j,k-1；
若最短路徑不經過點k，則di,j,k = di,j,k-1。
因此，di,j,k = min(di,k,k-1 dk,j,k-1 , di,j,k-1)。
在實際演算法中，為了節約空間，可以直接在原來空間上進行迭代，這樣空間可降至二維。
floyd-warshall演算法的描述如下：
for k ← 1 to n do
for i ← 1 to n do
for j ← 1 to n do
if (di,k dk,j < di,j) then
di,j ← di,k dk,j;
其中di,j表示由點i到點j的代價，當di,j為 ∞ 表示兩點之間沒有任何連接。
dijkstra
求單源、無負權的最短路。時效性較好，時間復雜度為o（v*v e）,可以用優先隊列進行優化，優化後時間復雜度變為0（v*lgn）。
源點可達的話，o（v*lgv e*lgv）=>o（e*lgv）。
當是稀疏圖的情況時，此時e=v*v/lgv，所以演算法的時間復雜度可為o（v^2） 。可以用優先隊列進行優化，優化後時間復雜度變為0（v*lgn）。
bellman-ford
求單源最短路，可以判斷有無負權迴路（若有，則不存在最短路），時效性較好，時間復雜度o（ve）。
bellman-ford演算法是求解單源最短路徑問題的一種演算法。
單源點的最短路徑問題是指：給定一個加權有向圖g和源點s，對於圖g中的任意一點v，求從s到v的最短路徑。
與dijkstra演算法不同的是，在bellman-ford演算法中，邊的權值可以為負數。設想從我們可以從圖中找到一個環
路（即從v出發，經過若干個點之後又回到v）且這個環路中所有邊的權值之和為負。那麼通過這個環路，環路中任意兩點的最短路徑就可以無窮小下去。如果不處理這個負環路，程序就會永遠運行下去。 而bellman-ford演算法具有分辨這種負環路的能力。
spfa
是bellman-ford的隊列優化，時效性相對好，時間復雜度o（ke）。（k< 與bellman-ford演算法類似，spfa演算法採用一系列的鬆弛操作以得到從某一個節點出發到達圖中其它所有節點的最短路徑。所不同的是，spfa演算法通過維護一個隊列，使得一個節點的當前最短路徑被更新之後沒有必要立刻去更新其他的節點，從而大大減少了重復的操作次數。
spfa演算法可以用於存在負數邊權的圖，這與dijkstra演算法是不同的。
與dijkstra演算法與bellman-ford演算法都不同，spfa的演算法時間效率是不穩定的，即它對於不同的圖所需要的時間有很大的差別。
在最好情形下，每一個節點都只入隊一次，則演算法實際上變為廣度優先遍歷，其時間復雜度僅為o(e)。另一方面，存在這樣的例子，使得每一個節點都被入隊(v-1)次，此時演算法退化為bellman-ford演算法，其時間復雜度為o(ve)。
spfa演算法在負邊權圖上可以完全取代bellman-ford演算法，另外在稀疏圖中也表現良好。但是在非負邊權圖中，為了避免最壞情況的出現，通常使用效率更加穩定的dijkstra演算法，以及它的使用堆優化的版本。通常的spfa。