堆优化版迪杰斯特拉算法：
- 优化原理：
上面的朴素版迪杰斯特拉算法主要缺陷是，每当找到一个最短路径，如果需要找下一个最短路径，就需要在完成松弛操作之后，遍历dist数组，寻找其中的最小值。遍历dist数组的时间复杂度为O(n)。（dist数组储存源点到各个点的当前最短距离）
如果图的边数为n*(n-1)，那么每找到一个最小值，所要进行的松弛操作数就是n-1，这和遍历dist数组可以同时进行，算法优化的空间不大。
然而，如果是稀疏图，每找到一个最小值，所要进行的松弛操作数就远小于n-1，这时就可以对算法进行优化。优化的关键是省去对dist的线性查找，如果每次可以直接返回dist中的最大值，就可以大大减小算法的时间复杂度。
堆优化后的迪杰斯特拉算法复杂度为mlogn
- 算法分析：
堆优化版迪杰斯特拉时间复杂度为O（mlogn）,n表示点数，m表示边数
-
- 初始化dist[1]=0，dist[i]=+∞ (除1外其它点)
-
- 循环遍历所有节点
-
-
- 找到当前未在s中标记过且离远点最近的点 （朴素：总共n^2次）---->（堆优化:总共n次）
- 该点进行标记
- 用t更新其它点的距离（朴素：O(n^2)）----->（堆优化：O（mlogn））
-
假设1为当源点
文章来源地址https://www.toymoban.com/news/detail-402184.html
- 找到当前标记过且离源点最近的1号点
- 标记1号点已确定的最短距离
- 用1号点的距离更新2号与3号点的距离
- 找到当前为标记过且离源点最近的2号点
- 找到2号以确定最段距离
- 用1号点的距离更新2号点与3号点（1+9<12）距离
依次类推得：
时间复杂度分析
每次找到最小距离的点沿着边更新其他的点，若dist[j] > distance + w[i]，表示可以更新dist[j]，更新后再把j点和对应的距离放入小根堆中。由于点的个数是n，边的个数是m，在极限情况下（稠密图m=n(n−1)2m=n(n−1)2）最多可以更新m回，每一回最多可以更新n个点（严格上是n - 1个点），有m回，因此最多可以把n2个点放入到小根堆中，因此每一次更新小根堆排序的情况是O(log(n2))，一共最多m次更新，因此总的时间复杂度上限是 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];// 存储1号点到每个点的最短距离
static boolean[] st = new boolean[N];
static int INF = 0x3f3f3f3f;//设置无穷大
public static void add(int a,int b,int c)
{
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++;
}
// 求1号点到n号点的最短路，如果不存在则返回-1
public static int dijkstra()
{
//维护当前未在st中标记过且离源点最近的点
PriorityQueue<PIIs> queue = new PriorityQueue<PIIs>();
Arrays.fill(dist, INF);
dist[1] = 0;
queue.add(new PIIs(0,1));
while(!queue.isEmpty())
{
//1、找到当前未在s中出现过且离源点最近的点
PIIs p = queue.poll();
int t = p.getSecond();
int distance = p.getFirst();
if(st[t]) continue;
//2、将该点进行标记
st[t] = true;
//3、用t更新其他点的距离
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());
}
}
文章来源：https://www.toymoban.com/news/detail-402184.html
到了这里，关于堆优化版迪杰斯特拉（Dijkstra）算法简单分析的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
