最短路问题分为俩个模块,单源最短路和多源最短路问题,而单源最短路中又分为4种算法,分别总结一下
单源最短路问题(又称为SSSP问题),给定一张有向图,n个点,m个边,节点以[1,n]之间的连续整数编号,(x,y,z)描述一条从x出发,到达y,长度为z的有向边。设1号点为起点,求长度为n的数组dist,其中dist[i]表示从起点1到节点i的最短路径的长度
算法的基本流程:
不难发现,基于贪心,故只适用于边的长度为非负
当边长都为非负数的时候,全局最小值已经不能被其他节点更新,故在第一步中选出的节点x必然满足:dist[x]已经是起点到x的最短路径,进行不断的选择,标记,拓展,最终得到每个节点的最短路径的长度
package 最短路;
public class Dijkstra {
/*
* 参数adjMatrix:为图的权重矩阵,权值为-1的两个顶点表示不能直接相连
* 函数功能:返回顶点0到其它所有顶点的最短距离,其中顶点0到顶点0的最短距离为0
*/
public int[] getShortestPaths(int[][] adjMatrix) {
int[] result = new int[adjMatrix.length]; //用于存放顶点0到其它顶点的最短距离
boolean[] used = new boolean[adjMatrix.length]; //用于判断顶点是否被遍历
used[0] = true; //表示顶点0已被遍历
for(int i = 1;i < adjMatrix.length;i++) {
result[i] = adjMatrix[0][i];
used[i] = false;
}
for(int i = 1;i < adjMatrix.length;i++) {
int min = Integer.MAX_VALUE; //用于暂时存放顶点0到i的最短距离,初始化为Integer型最大值
int k = 0;
for(int j = 1;j < adjMatrix.length;j++) { //找到顶点0到其它顶点中距离最小的一个顶点
if(!used[j] && result[j] != -1 && min > result[j]) {
min = result[j];
k = j;
}
}
used[k] = true; //将距离最小的顶点,记为已遍历
for(int j = 1;j < adjMatrix.length;j++) { //然后,将顶点0到其它顶点的距离与加入中间顶点k之后的距离进行比较,更新最短距离
if(!used[j]) { //当顶点j未被遍历时
//首先,顶点k到顶点j要能通行;这时,当顶点0到顶点j的距离大于顶点0到k再到j的距离或者顶点0无法直接到达顶点j时,更新顶点0到顶点j的最短距离
if(adjMatrix[k][j] != -1 && (result[j] > min + adjMatrix[k][j] || result[j] == -1))
result[j] = min + adjMatrix[k][j];
}
}
}
return result;
}
public static void main(String[] args) {
Dijkstra test = new Dijkstra();
int[][] adjMatrix = {{0,6,3,-1,-1,-1},
{6,0,2,5,-1,-1},
{3,2,0,3,4,-1},
{-1,5,3,0,2,3},
{-1,-1,4,2,0,5},
{-1,-1,-1,3,5,0}};
int[] result = test.getShortestPaths(adjMatrix);
System.out.println("顶点0到图中所有顶点之间的最短距离为:");
for(int i = 0;i < result.length;i++)
System.out.print(result[i]+" ");
}
}
基于迭代思想:
package 最短路;
import java.util.Scanner;
public class BellmanFord {
public long[] result; //用于存放第0个顶点到其它顶点之间的最短距离
//内部类,表示图的一条加权边
class edge {
public int a; //边的起点
public int b; //边的终点
public int value; //边的权值
edge(int a, int b, int value) {
this.a = a;
this.b = b;
this.value = value;
}
}
//返回第0个顶点到其它所有顶点之间的最短距离
public boolean getShortestPaths(int n, edge[] A) {
result = new long[n];
for (int i = 1; i < n; i++)
result[i] = Integer.MAX_VALUE; //初始化第0个顶点到其它顶点之间的距离为无穷大,此处用Integer型最大值表示
for (int i = 1; i < n; i++) {
for (int j = 0; j < A.length; j++) {
if (result[A[j].b] > result[A[j].a] + A[j].value)
result[A[j].b] = result[A[j].a] + A[j].value;
}
}
boolean judge = true;
for (int i = 1; i < n; i++) { //判断给定图中是否存在负环
if (result[A[i].b] > result[A[i].a] + A[i].value) {
judge = false;
break;
}
}
return judge;
}
public static void main(String[] args) {
BellmanFord test = new BellmanFord();
Scanner in = new Scanner(System.in);
System.out.println("请输入一个图的顶点总数n和边总数p:");
int n = in.nextInt();
int p = in.nextInt();
edge[] A = new edge[p];
System.out.println("请输入具体边的数据:");
for (int i = 0; i < p; i++) {
int a = in.nextInt();
int b = in.nextInt();
int value = in.nextInt();
A[i] = test.new edge(a, b, value);
}
if (test.getShortestPaths(n, A)) {
for (int i = 0; i < test.result.length; i++)
System.out.print(test.result[i] + " ");
} else
System.out.println("给定图存在负环,没有最短距离");
}
}
实际上,SPFA算法在国际上统称为“队列优化的Bellman-Ford算法,仅在中国称为”SPFA“算法 流程如下:
package 最短路;
import java.util.ArrayList;
import java.util.Scanner;
public class SPFA {
public long[] result; //用于得到第s个顶点到其它顶点之间的最短距离
//内部类,用于存放图的具体边数据
class edge {
public int a; //边的起点
public int b; //边的终点
public int value; //边的权值
edge(int a, int b, int value) {
this.a = a;
this.b = b;
this.value = value;
}
}
/*
* 参数n:给定图的顶点个数
* 参数s:求取第s个顶点到其它所有顶点之间的最短距离
* 参数edge:给定图的具体边
* 函数功能:如果给定图不含负权回路,则可以得到最终结果,如果含有负权回路,则不能得到最终结果
*/
public boolean getShortestPaths(int n, int s, edge[] A) {
ArrayList<Integer> list = new ArrayList<Integer>();
result = new long[n];
boolean[] used = new boolean[n];
int[] num = new int[n];
for(int i = 0;i < n;i++) {
result[i] = Integer.MAX_VALUE;
used[i] = false;
}
result[s] = 0; //第s个顶点到自身距离为0
used[s] = true; //表示第s个顶点进入数组队
num[s] = 1; //表示第s个顶点已被遍历一次
list.add(s); //第s个顶点入队
while(list.size() != 0) {
int a = list.get(0); //获取数组队中第一个元素
list.remove(0); //删除数组队中第一个元素
for(int i = 0;i < A.length;i++) {
//当list数组队的第一个元素等于边A[i]的起点时
if(a == A[i].a && result[A[i].b] > result[A[i].a] + A[i].value) {
result[A[i].b] = result[A[i].a] + A[i].value;
if(!used[A[i].b]) {
list.add(A[i].b);
num[A[i].b]++;
if(num[A[i].b] > n)
return false;
used[A[i].b] = true; //表示边A[i]的终点b已进入数组队
}
}
}
used[a] = false; //顶点a出数组对
}
return true;
}
public static void main(String[] args) {
SPFA test = new SPFA();
Scanner in = new Scanner(System.in);
System.out.println("请输入一个图的顶点总数n起点下标s和边总数p:");
int n = in.nextInt();
int s = in.nextInt();
int p = in.nextInt();
edge[] A = new edge[p];
System.out.println("请输入具体边的数据:");
for(int i = 0;i < p;i++) {
int a = in.nextInt();
int b = in.nextInt();
int value = in.nextInt();
A[i] = test.new edge(a, b, value);
}
if(test.getShortestPaths(n, s, A)) {
for(int i = 0;i < test.result.length;i++)
System.out.print(test.result[i]+" ");
} else
System.out.println("给定图存在负环,没有最短距离");
}
}