图的最短路径算法——《啊哈！算法》

2024-09-09 04:32

文章标签 算法路径啊哈

本文主要是介绍图的最短路径算法——《啊哈！算法》，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

图的实现方式

在这里插入图片描述

邻接矩阵法

int[][] map;
// 图的邻接矩阵存储法
map = new int[5][5];
map[0] = new int[] {0, 1, 2, 3, 4};
map[1] = new int[] {1, 0, 2, 6, 4};
map[2] = new int[] {2, 999, 0, 3, 999};
map[3] = new int[] {3, 7, 999, 0, 1};
map[4] = new int[] {4, 5, 999, 12, 0};

邻接表

  // 顶点的第一条线的下标int[] first;// 顶点线的下一哥int[] next;int[] u;int[] v;int[] w;//顶点说int n;//线条数int m;n = 5;m = 8;int[][] data = new int[m + 1][2];data[0] = new int[] {0, 0, 0};data[1] = new int[] {1, 4, 4};data[2] = new int[] {1, 3, 6};data[3] = new int[] {1, 2, 2};data[4] = new int[] {2, 3, 3};data[5] = new int[] {3, 1, 7};data[6] = new int[] {3, 4, 1};data[7] = new int[] {4, 3, 12};data[8] = new int[] {4, 1, 5};first = new int[n + 1];next = new int[m + 1];u = new int[m + 1];v = new int[m + 1];w = new int[m + 1];for (int i = 1; i <= m; i++) {u[i] = data[i][0];v[i] = data[i][1];w[i] = data[i][2];next[i] = first[u[i]];first[u[i]] = i;}

最短路径算法

Floyd

核心代码

 for (int k = 1; k <= 4; k++) {for (int i = 1; i <= 4; i++) {for (int j = 1; j <= 4; j++) {if (newMap[i][k] + newMap[k][j] < newMap[i][j]) {newMap[i][j] = newMap[i][k] + newMap[k][j];}}}}

Dijkstra

核心代码

//除去0位置标记
book[0] = 1;// 初始化dis
System.arraycopy(map[start], 1, dis, 1, 6);
// 第一个顶点就是确定的点
book[start] = 1;
count++;
for (int i = 1; i <= 6 - 1; i++) {// 确定新的点int min = 7;int minMap = 9999;for (int j = 1; j <= 6; j++) {if (book[j] == 1) {continue;}if (minMap > dis[j]) {min = j;minMap = dis[j];}}book[min] = 1;// 松弛for (int k = 1; k <= 6; k++) {if (book[k] == 1) {continue;}if (dis[k] > dis[min] + map[min][k]) {dis[k] = dis[min] + map[min][k];}}}

Bellman-Ford

核心代码

Arrays.fill(dis, 2, dis.length, 999);
// 核心算法
// 进行n-1次松弛，得到经过n-1个点（除了第一个点）后的所有点的松弛后的最小路径图
for (int k = 1; k <= n - 1; k++) {isBreak = true;for (int i = 1; i <= m; i++) {if (dis[v[i]] > dis[u[i]] + w[i]) {dis[v[i]] = dis[u[i]] + w[i];}}
}

队列优化的Bellman-Ford

核心代码

 Arrays.fill(dis, 1, dis.length, 999);dis[start] = 0;int[] que = new int[n * m + 1];int head = 0, tail = 0;que[tail] = start;tail++;book[start] = 1;while (head < tail) {// 遍历每个边int index = first[que[head]];while (index != -1) {// 松弛if (dis[v[index]] > dis[u[index]] + w[index]) {dis[v[index]] = dis[u[index]] + w[index];if (book[v[index]] == 0) {book[v[index]] = 1;que[tail] = v[index];tail++;}}index = next[index];}book[que[head]] = 0;head++;}

比较

	Floyd	Dijkstra	Bellman-Ford	队列优化的Bellman-Ford
空间复杂度	O(NN)	O(M)	O(NM)	O(M)
时间复杂度	O(NNN)	O((M+N)logN)	O(NM)	O(M)~O(NM)
适用情况	稠密图和顶点关系密切	稠密图和顶点关系密切	稀疏图和边关系密切	稀疏图和边关系密切
负权	可以解决负权	不能解决负权	可以解决负权	可以解决负权
有负权边	可以处理	不能处理	可以处理	可以处理
判断是否存在负权回路	不能	不能	可以判定	可以判定