演算法最短路

㈠ 圖論：最短路演算法有哪些以及它們的比較

請先檢查你matlab的版本，這里提示沒有找到該函數。很可能是因為matlab的版本太老。
由於這個函數是計算生物學工具箱的，估計早期的版本沒有這個工具箱。
我這個函數是在2008版本下編寫的，用2031a版的是沒問題的。
ps:matlab每一版都會增減和優化一些函數，建議盡可能的保持高版本。

㈡ 最短路徑演算法

Dijkstra演算法，A*演算法和D*演算法

Dijkstra演算法是典型最短路演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法能得出最短路徑的最優解，但由於它遍歷計算的節點很多，所以效率低。

Dijkstra演算法是很有代表性的最短路演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。

Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表方式，Drew為了和下面要介紹的 A* 演算法和 D* 演算法表述一致，這里均採用OPEN,CLOSE表的方式。

大概過程：
創建兩個表，OPEN, CLOSE。
OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
1． 訪問路網中里起始點最近且沒有被檢查過的點，把這個點放入OPEN組中等待檢查。
2． 從OPEN表中找出距起始點最近的點，找出這個點的所有子節點，把這個點放到CLOSE表中。
3． 遍歷考察這個點的子節點。求出這些子節點距起始點的距離值，放子節點到OPEN表中。
4． 重復2，3，步。直到OPEN表為空，或找到目標點。

提高Dijkstra搜索速度的方法很多，常用的有數據結構採用Binary heap的方法，和用Dijkstra從起始點和終點同時搜索的方法。

A*（A-Star)演算法是一種啟發式演算法，是靜態路網中求解最短路最有效的方法。

公式表示為： f(n)=g(n)+h(n),
其中f(n) 是節點n從初始點到目標點的估價函數，
g(n) 是在狀態空間中從初始節點到n節點的實際代價，
h(n)是從n到目標節點最佳路徑的估計代價。

保證找到最短路徑（最優解的）條件，關鍵在於估價函數h(n)的選取：
估價值h(n)<= n到目標節點的距離實際值，這種情況下，搜索的點數多，搜索范圍大，效率低。但能得到最優解。
如果 估價值>實際值, 搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解。
估價值與實際值越接近，估價函數取得就越好。
例如對於幾何路網來說，可以取兩節點間歐幾理德距離（直線距離）做為估價值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；這樣估價函數f在g值一定的情況下，會或多或少的受估價值h的制約，節點距目標點近，h值小，f值相對就小，能保證最短路的搜索向終點的方向進行。明顯優於Dijstra演算法的毫無無方向的向四周搜索。
conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible
主要搜索過程：
創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
遍歷當前節點的各個節點，將n節點放入CLOSE中，取n節點的子節點X,->算X的估價值->
While(OPEN!=NULL)
{
從OPEN表中取估價值f最小的節點n;
if(n節點==目標節點) break;
else
{
if(X in OPEN) 比較兩個X的估價值f //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於OPEN表的估價值 )
更新OPEN表中的估價值; //取最小路徑的估價值
if(X in CLOSE) 比較兩個X的估價值 //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於CLOSE表的估價值 )
更新CLOSE表中的估價值; 把X節點放入OPEN //取最小路徑的估價值
if(X not in both)
求X的估價值;
並將X插入OPEN表中; //還沒有排序
}
將n節點插入CLOSE表中;
按照估價值將OPEN表中的節點排序; //實際上是比較OPEN表內節點f的大小，從最小路徑的節點向下進行。
}

A*演算法和Dijistra演算法的區別在於有無估價值，Dijistra演算法相當於A*演算法中估價值為0的情況。

動態路網，最短路演算法 D*A* 在靜態路網中非常有效（very efficient for static worlds），但不適於在動態路網，環境如權重等不斷變化的動態環境下。

D*是動態A*（D-Star,Dynamic A*） 卡內及梅隆機器人中心的Stentz在1994和1995年兩篇文章提出，主要用於機器人探路。是火星探測器採用的尋路演算法。

主要方法：
1.先用Dijstra演算法從目標節點G向起始節點搜索。儲存路網中目標點到各個節點的最短路和該位置到目標點的實際值h,k（k為所有變化h之中最小的值,當前為k=h。每個節點包含上一節點到目標點的最短路信息1(2),2(5),5(4)，4（7）。則1到4的最短路為1-2-5-4。
原OPEN和CLOSE中節點信息保存。
2.機器人沿最短路開始移動，在移動的下一節點沒有變化時，無需計算，利用上一步Dijstra計算出的最短路信息從出發點向後追述即可，當在Y點探測到下一節點X狀態發生改變，如堵塞。機器人首先調整自己在當前位置Y到目標點G的實際值h(Y)，h(Y)=X到Y的新權值c(X,Y)+X的原實際值h(X).X為下一節點(到目標點方向Y->X->G），Y是當前點。k值取h值變化前後的最小。
3.用A*或其它演算法計算，這里假設用A*演算法,遍歷Y的子節點，點放入CLOSE,調整Y的子節點a的h值，h(a)=h(Y)+Y到子節點a的權重C(Y,a),比較a點是否存在於OPEN和CLOSE中，方法如下：
while()
{
從OPEN表中取k值最小的節點Y;
遍歷Y的子節點a,計算a的h值 h(a)=h(Y)+Y到子節點a的權重C(Y,a)
{
if(a in OPEN) 比較兩個a的h值
if( a的h值小於OPEN表a的h值 )
{ 更新OPEN表中a的h值;k值取最小的h值
有未受影響的最短路經存在
break;
}
if(a in CLOSE) 比較兩個a的h值 //注意是同一個節點的兩個不同路徑的估價值
if( a的h值小於CLOSE表的h值 )
{
更新CLOSE表中a的h值; k值取最小的h值;將a節點放入OPEN表
有未受影響的最短路經存在
break;
}
if(a not in both)
將a插入OPEN表中; //還沒有排序
}
放Y到CLOSE表；
OPEN表比較k值大小進行排序；
}
機器人利用第一步Dijstra計算出的最短路信息從a點到目標點的最短路經進行。

D*演算法在動態環境中尋路非常有效，向目標點移動中，只檢查最短路徑上下一節點或臨近節點的變化情況，如機器人尋路等情況。對於距離遠的最短路徑上發生的變化，則感覺不太適用。

㈢ 關於圖的最短路演算法

可以算出任意一個確定頂點到任意節點的單源最短路徑.
要證明么?好像不太說的清楚....

寫起來也確實比Dijkstra演算法簡單,而且是很標準的o(n^2),
但顯然是Dijkstra演算法的效率稍微高一些.....

㈣ 幫忙講一下最短路演算法的過程，比如在一個圖上怎麼求出最短路，舉個例子。

比如有一直線CD，CD是河，CD上邊有AB兩個點，分別到河邊不同距離，現在要去河邊打水，問從哪去打水距離最近？
從A出發的話以河為中間分界線，鏡像A'到對面，然後A'－B連線，A'B直線跟CD交界點打水就是最近距離，如果由B出發的話原理一樣，也可以鏡像出B'連成AB'畫出一交界點也是最近的打水點，

㈤ dijkstra 的MATLAB演算法 最短路

9個客戶點，1個車場。需求與距離已給，完成車場到各客戶點及各個點對之間的最短路。假設運輸單價為1，根據需求和最短路計算運輸費用（我一直沒弄懂需求與最短路有什麼關系）。
已知的是各點的XY坐標與各點的需求（第一個點位車場，其餘9個點為客戶點，需求里第一個點不用管）
若出現距離小於10，在原距離基礎上加10
x=[8 12 14 16 4 2 8 8 9 10;]
y=[3 9 4 9 12 14 16 18 13 15;]
demand=[2 13 18 10 9 1 12 4 1 3;](第一個數不用管)
鄰接矩陣為
path_g =

0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 0 1 0 1 0 0
0 0 0 0 0 0 1 1 1 0
1 1 0 0 0 1 1 0 1 0
0 0 1 0 1 0 0 0 0 0
1 1 0 1 1 0 0 0 0 0
1 1 1 1 0 0 0 0 1 1
1 1 0 1 1 0 0 1 0 0
0 0 0 0 0 0 0 1 0 0
數據不重要，主要是方法！！！
發過去了

㈥ 對於網路中有負權弧時，可以使用哪種演算法求取最短路

現在比較常用的最短路演算法是dijkstra它的使用條件是你會寫，且圖中無負權邊

SPFA是現在稀疏圖上常用最短路演算法，且無負環，而且你要會寫
floyd是當前求多源最短路的常用演算法
對於程序猿來說，dijkstra性能穩定比較changyong
對於oier來說，只要不是稠密圖，一定寫spfa，因為spfa在稀疏圖上太快了

㈦ 最短路演算法和最小生成樹演算法有什麼區別

兩個演算法沒有什麼太多的聯系，只能說是想法類似，都用了一定程度的貪心思維。
最短路是要求一點到另外的點的最短路徑，只要最短的長度到達就好，除了出發點和終點外一概不管。如果不求一點到所有點的最短路，甚至可以不管所有點是否都聯通。
最小生成樹則要保證第一所有點都是聯通的，不然就稱不上是樹了，而後保證樹的邊長度之和最小。

㈧ Prim演算法可以求最短路嗎

不能。Prim是求最小生成樹的演算法，不能等效為最短路徑。如圖(參考自《王道考研系列——數據結構》)

但是Dijkstra演算法，和Floyd演算法可以求最短路徑。

㈨ C語言實現最短路問題的演算法

＃i nclude<stdio.h>
＃i nclude <stdlib.h>
//Dijkstra演算法實現函數
void Dijkstra(int n,int v,int dist[],int prev[],int **cost)
{
int i;
int j;
int maxint = 65535;//定義一個最大的數值，作為不相連的兩個節點的代價權值
int *s ;//定義具有最短路徑的節點子集s
s = (int *)malloc(sizeof(int) * n);
//初始化最小路徑代價和前一跳節點值
for (i = 1; i <= n; i++)
{
dist[i] = cost[v][i];
s[i] = 0;
if (dist[i] == maxint)
{
prev[i] = 0;
}
else
{
prev[i] = v;
}
}
dist[v] = 0;
s[v] = 1;//源節點作為最初的s子集
for (i = 1; i < n; i++)
{
int temp = maxint;
int u = v;
//加入具有最小代價的鄰居節點到s子集
for (j = 1; j <= n; j++)
{
if ((!s[j]) && (dist[j] < temp))
{
u = j;
temp = dist[j];
}
}
s[u] = 1;
//計算加入新的節點後，更新路徑使得其產生代價最短
for (j = 1; j <= n; j++)
{
if ((!s[j]) && (cost[u][j] < maxint))
{
int newdist = dist[u] + cost[u][j];
if (newdist < dist[j])
{
dist[j] = newdist;
prev[j] = u;
}
}
}
}
}
//展示最佳路徑函數
void ShowPath(int n,int v,int u,int *dist,int *prev)
{
int j = 0;
int w = u;
int count = 0;
int *way ;
way=(int *)malloc(sizeof(int)*(n+1));
//回溯路徑
while (w != v)
{
count++;
way[count] = prev[w];
w = prev[w];
}
//輸出路徑
printf("the best path is:\n");
for (j = count; j >= 1; j--)
{
printf("%d -> ",way[j]);
}
printf("%d\n",u);
}
//主函數，主要做輸入輸出工作
void main()
{
int i,j,t;
int n,v,u;

int **cost;//代價矩陣
int *dist;//最短路徑代價
int *prev;//前一跳節點空間
printf("please input the node number: ");
scanf("%d",&n);
printf("please input the cost status:\n");

cost=(int **)malloc(sizeof(int)*(n+1));
for (i = 1; i <= n; i++)
{
cost[i]=(int *)malloc(sizeof(int)*(n+1));
}
//輸入代價矩陣
for (j = 1; j <= n; j++)
{
for (t = 1; t <= n; t++)
{
scanf("%d",&cost[j][t]);
}
}

dist = (int *)malloc(sizeof(int)*n);
prev = (int *)malloc(sizeof(int)*n);
printf("please input the source node: ");
scanf("%d",&v);
//調用dijkstra演算法
Dijkstra(n, v, dist, prev, cost);
printf("*****************************\n");
printf("have confirm the best path\n");
printf("*****************************\n");
for(i = 1; i <= n ; i++)
{
if(i!=v)
{
printf("the distance cost from node %d to node %d is %d\n",v,i,dist[i]);
printf("the pre-node of node %d is node %d \n",i,prev[i]);
ShowPath(n,v,i, dist, prev);
}
}
}