堆優(yōu)化版迪杰斯特拉算法：
- 優(yōu)化原理：
上面的樸素版迪杰斯特拉算法主要缺陷是，每當(dāng)找到一個(gè)最短路徑，如果需要找下一個(gè)最短路徑，就需要在完成松弛操作之后，遍歷dist數(shù)組，尋找其中的最小值。遍歷dist數(shù)組的時(shí)間復(fù)雜度為O(n)。（dist數(shù)組儲(chǔ)存源點(diǎn)到各個(gè)點(diǎn)的當(dāng)前最短距離）
如果圖的邊數(shù)為n*(n-1)，那么每找到一個(gè)最小值，所要進(jìn)行的松弛操作數(shù)就是n-1，這和遍歷dist數(shù)組可以同時(shí)進(jìn)行，算法優(yōu)化的空間不大。
然而，如果是稀疏圖，每找到一個(gè)最小值，所要進(jìn)行的松弛操作數(shù)就遠(yuǎn)小于n-1，這時(shí)就可以對(duì)算法進(jìn)行優(yōu)化。優(yōu)化的關(guān)鍵是省去對(duì)dist的線性查找，如果每次可以直接返回dist中的最大值，就可以大大減小算法的時(shí)間復(fù)雜度。
堆優(yōu)化后的迪杰斯特拉算法復(fù)雜度為mlogn
- 算法分析：
堆優(yōu)化版迪杰斯特拉時(shí)間復(fù)雜度為O（mlogn）,n表示點(diǎn)數(shù)，m表示邊數(shù)
-
- 初始化dist[1]=0，dist[i]=+∞ (除1外其它點(diǎn))
-
- 循環(huán)遍歷所有節(jié)點(diǎn)
-
-
- 找到當(dāng)前未在s中標(biāo)記過(guò)且離遠(yuǎn)點(diǎn)最近的點(diǎn) （樸素：總共n^2次）---->（堆優(yōu)化:總共n次）
- 該點(diǎn)進(jìn)行標(biāo)記
- 用t更新其它點(diǎn)的距離（樸素：O(n^2)）----->（堆優(yōu)化：O（mlogn））
-
假設(shè)1為當(dāng)源點(diǎn)
?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-402184.html
- 找到當(dāng)前標(biāo)記過(guò)且離源點(diǎn)最近的1號(hào)點(diǎn)
- 標(biāo)記1號(hào)點(diǎn)已確定的最短距離
- 用1號(hào)點(diǎn)的距離更新2號(hào)與3號(hào)點(diǎn)的距離
- 找到當(dāng)前為標(biāo)記過(guò)且離源點(diǎn)最近的2號(hào)點(diǎn)
- 找到2號(hào)以確定最段距離
- 用1號(hào)點(diǎn)的距離更新2號(hào)點(diǎn)與3號(hào)點(diǎn)（1+9<12）距離
依次類推得：
?
?時(shí)間復(fù)雜度分析
每次找到最小距離的點(diǎn)沿著邊更新其他的點(diǎn)，若dist[j] > distance + w[i]，表示可以更新dist[j]，更新后再把j點(diǎn)和對(duì)應(yīng)的距離放入小根堆中。由于點(diǎn)的個(gè)數(shù)是n，邊的個(gè)數(shù)是m，在極限情況下（稠密圖m=n(n?1)2m=n(n?1)2）最多可以更新m回，每一回最多可以更新n個(gè)點(diǎn)（嚴(yán)格上是n - 1個(gè)點(diǎn)），有m回，因此最多可以把n2個(gè)點(diǎn)放入到小根堆中，因此每一次更新小根堆排序的情況是O(log(n2))，一共最多m次更新，因此總的時(shí)間復(fù)雜度上限是 O(mlog((n2)))=O(2mlogn)=O(mlogn)
算法代碼
?
public class Main{
static int N = 100010;
static int n;
static int[] h = new int[N];
static int[] e = new int[N];
static int[] ne = new int[N];
static int[] w = new int[N];
static int idx = 0;
static int[] dist = new int[N];// 存儲(chǔ)1號(hào)點(diǎn)到每個(gè)點(diǎn)的最短距離
static boolean[] st = new boolean[N];
static int INF = 0x3f3f3f3f;//設(shè)置無(wú)窮大
public static void add(int a,int b,int c)
{
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++;
}
// 求1號(hào)點(diǎn)到n號(hào)點(diǎn)的最短路，如果不存在則返回-1
public static int dijkstra()
{
//維護(hù)當(dāng)前未在st中標(biāo)記過(guò)且離源點(diǎn)最近的點(diǎn)
PriorityQueue<PIIs> queue = new PriorityQueue<PIIs>();
Arrays.fill(dist, INF);
dist[1] = 0;
queue.add(new PIIs(0,1));
while(!queue.isEmpty())
{
//1、找到當(dāng)前未在s中出現(xiàn)過(guò)且離源點(diǎn)最近的點(diǎn)
PIIs p = queue.poll();
int t = p.getSecond();
int distance = p.getFirst();
if(st[t]) continue;
//2、將該點(diǎn)進(jìn)行標(biāo)記
st[t] = true;
//3、用t更新其他點(diǎn)的距離
for(int i = h[t];i != -1;i = ne[i])
{
int j = e[i];
if(dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
queue.add(new PIIs(dist[j],j));
}
}
}
if(dist[n] == INF) return -1;
return dist[n];
}
public static void main(String[] args) throws IOException{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] str1 = reader.readLine().split(" ");
n = Integer.parseInt(str1[0]);
int m = Integer.parseInt(str1[1]);
Arrays.fill(h, -1);
while(m -- > 0)
{
String[] str2 = reader.readLine().split(" ");
int a = Integer.parseInt(str2[0]);
int b = Integer.parseInt(str2[1]);
int c = Integer.parseInt(str2[2]);
add(a,b,c);
}
System.out.println(dijkstra());
}
}
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-402184.html
?
到了這里，關(guān)于堆優(yōu)化版迪杰斯特拉（Dijkstra）算法簡(jiǎn)單分析的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
