最短路徑算法在現(xiàn)實(shí)生活中也具有非常多的應(yīng)用，例如在一個(gè)復(fù)雜的景區(qū)棕洋，想要從一個(gè)景點(diǎn)到另外一個(gè)景點(diǎn)遂庄，利用最短路徑算法就可以找到最短的路程，而如果不做規(guī)劃就隨緣前往塔拳，可能會(huì)繞很多路才能到達(dá)鼠证，雖然到了，但是精力都花費(fèi)在走路上了靠抑，更別說去觀光景點(diǎn)了名惩。
-
Dijkstra算法：
-
算法思想分析：
算法從一個(gè)點(diǎn)開始，向周圍擴(kuò)散孕荠，每次去尋找一個(gè)確定了最短路徑的點(diǎn)娩鹉，并且同時(shí)更新所有點(diǎn)的最短路徑距離，直到所有點(diǎn)都被找到最短路徑 - 算法具體代碼：
-
算法思想分析：
#define MAX 100
#define INF 32767
int tempMatrix[MAX][MAX]; // 鄰接矩陣
int mVexNum; // 頂點(diǎn)數(shù)量
void dijkstra(int start, int prev[], int dist[])
{
int i,j,k = 0;
int min;
int tmp;
int flag[MAX]; // flag[i] = 1 表示"頂點(diǎn)vs"到"頂點(diǎn)i"的最短路徑已成功獲取稚伍。
// 初始化
for (i = 0; i < mVexNum; i++)
{
flag[i] = 0; // 頂點(diǎn)i的最短路徑還沒獲取到弯予。
prev[i] = 0; // 頂點(diǎn)i的前驅(qū)頂點(diǎn)為0。
dist[i] = tempMatrix[start][i]; // 頂點(diǎn)i的最短路徑為"頂點(diǎn)start"到"頂點(diǎn)i"的權(quán)个曙。
}
// 對(duì)"頂點(diǎn)start"自身進(jìn)行初始化
flag[start] = 1;
dist[start] = 0;
// 遍歷mVexNum-1次锈嫩；每次找出一個(gè)頂點(diǎn)的最短路徑。
for (i = 1; i < mVexNum; i++)
{
// 尋找當(dāng)前最小的路徑垦搬；
// 即呼寸，在未獲取最短路徑的頂點(diǎn)中，找到離start最近的頂點(diǎn)(k)猴贰。
min = INF;
for (j = 0; j < mVexNum; j++)
{
if (flag[j] == 0 && dist[j] < min)
{
min = dist[j];
k = j;
}
}
// 標(biāo)記"頂點(diǎn)k"為已經(jīng)獲取到最短路徑
flag[k] = 1;
// 修正當(dāng)前最短路徑和前驅(qū)頂點(diǎn)
// 即对雪，當(dāng)已經(jīng)知道"頂點(diǎn)k的最短路徑"之后，更新"未獲取最短路徑的頂點(diǎn)的最短路徑和前驅(qū)頂點(diǎn)"米绕。
for (j = 0; j < mVexNum; j++)
{
tmp = (tempMatrix[k][j] == INF ? INF : (min + tempMatrix[k][j]));
if (flag[j] == 0 && (tmp < dist[j]))
{
dist[j] = tmp;
prev[j] = k;
}
}
}
}
-
算法細(xì)節(jié)分析：
算法中用到了三個(gè)數(shù)組瑟捣，分別是：- prev [ ]：用來存儲(chǔ)每個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)
- dist [ ]：用來存儲(chǔ)每個(gè)節(jié)點(diǎn)的最短路徑距離
- flag [ ]：輔助數(shù)組，用來存儲(chǔ)每個(gè)節(jié)點(diǎn)是否已經(jīng)找到了最短路徑
算法中用到了三次循環(huán)栅干，分別是：
- 第一次：循環(huán)了N-1次迈套，目的是每次循環(huán)都找到一個(gè)節(jié)點(diǎn)的最短路徑
- 第二次：循環(huán)了N次，目的是找到目前距離起始點(diǎn)最近的點(diǎn)碱鳞，然后標(biāo)記為已經(jīng)找到最短路徑
- 第三次：循環(huán)了N次桑李，由于新加入了一個(gè)確定了最短路徑的節(jié)點(diǎn)，那么原來的節(jié)點(diǎn)的最短路徑將有可能被更新窿给，所以這個(gè)循環(huán)的目的就是更新所有的節(jié)點(diǎn)的最短路徑的距離贵白，如果發(fā)現(xiàn)了更短路徑，同時(shí)也會(huì)將前驅(qū)節(jié)點(diǎn)更新
回首在最小生成樹算法中的Prim算法填大，這兩者的過程十分相似戒洼，那兩者的差別點(diǎn)在哪里呢？
-
與Prim算法的相同點(diǎn)和不同點(diǎn)：
-
相同點(diǎn)：
- prev [ ] 數(shù)組和flag [ ] 數(shù)組是一樣的允华，在兩個(gè)算法中均有一個(gè)用來存儲(chǔ)前驅(qū)節(jié)點(diǎn)的數(shù)組圈浇，目的是為了在算法進(jìn)行完之后將路徑打印出來，另外一個(gè)用來存儲(chǔ)每個(gè)節(jié)點(diǎn)是否被確定靴寂。
- 有兩次循環(huán)是一樣的磷蜀，第一次循環(huán)都是為了每次確定一個(gè)點(diǎn)，最后一次循環(huán)百炬，也都是因?yàn)橛行碌狞c(diǎn)被確定了褐隆，所以需要更新其他節(jié)點(diǎn)的狀態(tài)
-
不同點(diǎn)：
- 在Dijkstra算法中使用一個(gè)數(shù)組來存儲(chǔ)每個(gè)節(jié)點(diǎn)的最短路徑距離，而在Prim算法中使用一個(gè)數(shù)組來存儲(chǔ)節(jié)點(diǎn)到最小生成樹中的節(jié)點(diǎn)的最短距離
- 在Dijkstra算法中的第二個(gè)循環(huán)是來找目前離起始點(diǎn)最短距離的點(diǎn)剖踊，而在Prim算法中的第二個(gè)循環(huán)是用來找目前離最小生成樹中的節(jié)點(diǎn)距離最近的點(diǎn)
-
相同點(diǎn)：
-
Floyd算法
-
算法思想分析：
Floyd算法的過程建立在一個(gè)矩陣中庶弃，這個(gè)矩陣存儲(chǔ)的是各個(gè)點(diǎn)之間的距離衫贬，對(duì)于每個(gè)點(diǎn)進(jìn)行一次循環(huán)，這個(gè)循環(huán)過程中做的事情就是去尋找通過該節(jié)點(diǎn)的邊是否小于原本存儲(chǔ)在矩陣中的值歇攻，如果小于固惯，則更新 - 算法的具體代碼：
-
算法思想分析：
#define MAX 100
#define INF 32767
int mVexNum; // 頂點(diǎn)數(shù)
int mMatrix[MAX][MAX]; // 鄰接矩陣
void floyd(int path[][MAX], int dist[][MAX])
{
int i,j,k;
int tmp;
// 初始化
for (i = 0; i < mVexNum; i++)
{
for (j = 0; j < mVexNum; j++)
{
dist[i][j] = mMatrix[i][j]; // "頂點(diǎn)i"到"頂點(diǎn)j"的路徑長(zhǎng)度為"i到j(luò)的權(quán)值"。
path[i][j] = j; // "頂點(diǎn)i"到"頂點(diǎn)j"的最短路徑是經(jīng)過頂點(diǎn)j缴守。
}
}
// 計(jì)算最短路徑
for (k = 0; k < mVexNum; k++)
{
for (i = 0; i < mVexNum; i++)
{
for (j = 0; j < mVexNum; j++)
{
// 如果經(jīng)過下標(biāo)為k頂點(diǎn)路徑比原兩點(diǎn)間路徑更短葬毫，則更新dist[i][j]和path[i][j]
tmp = (dist[i][k]==INF || dist[k][j]==INF) ? INF : (dist[i][k] + dist[k][j]);
if (dist[i][j] > tmp)
{
// "i到j(luò)最短路徑"對(duì)應(yīng)的值設(shè)，為更小的一個(gè)(即經(jīng)過k)
dist[i][j] = tmp;
// "i到j(luò)最短路徑"對(duì)應(yīng)的路徑屡穗，經(jīng)過k
path[i][j] = path[i][k];
}
}
}
}
}
-
算法的細(xì)節(jié)分析：
算法中用到了兩個(gè)數(shù)組：- dist [ ]：這個(gè)二維數(shù)組用來存儲(chǔ)兩個(gè)節(jié)點(diǎn)之間的最短路徑距離
- path [ ]：這個(gè)數(shù)組用來存儲(chǔ)兩個(gè)節(jié)點(diǎn)之間的最短路徑將會(huì)經(jīng)過的點(diǎn)贴捡，目的是用來存儲(chǔ)最短路徑
算法中用到了三次循環(huán)：
- 第一次循環(huán)：第一次循環(huán)N次，對(duì)于每個(gè)點(diǎn)都需要進(jìn)行更新表的操作
- 第二次循環(huán)和第三次循環(huán)：這兩次循環(huán)實(shí)際上是對(duì)矩陣的一個(gè)遍歷操作
