Java有向无权图的单源点最短路径-邻接矩阵和邻接表_无权最短路径算法java实现

引入

此文章是随手笔记，写的不好见谅。

1. 无权图的单源点最短路径我这用BFS实现
2. 主要的就是图的实现与BFS的搜索，其它没什么
3. 为了下一步的有向有权图单源点最短路径做基础

代码

1.用邻接矩阵表示图的

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class MatrixShortestPath {
	static int n;// 点数
	static int e;// 边数
	static int G[][];// 领接矩阵
	static int dis[];// 路径 dis[i] = j, 默认1到节点i最短路径j
	static int path[];// 记录路线
	
	// BFS最短路径
	public static void Bfs(int u){
		path[u] = -1;// 起点
		// 源点 初始化为访问过
		dis[u] = 0;
		Queue<Integer> qu = new LinkedList<Integer>();// 队列
		qu.offer(u);// 添加源点进入
		while(!qu.isEmpty()){
			u = qu.poll();// 弹出最早的
			// 以u点扩散
			for(int i = 1; i <= n; i++){
				/*
				dis[i] == -1：代表是否访问过
				因为无权图，边权值默认为1，不用判断出现的节点k使，节点i到节点j的长度 > 节点i到节点k + 节点k到节点j的长度
				G[u][i] == 1，点u到点i存在路径
				*/
				if(dis[i] == -1 && G[u][i] == 1){
					// 更新路径：为源点到点u的路径+1，因为无权图，只需+1
					dis[i] = dis[u] + 1;
					// 记录路径
					path[i] = u;
					// 添加到队列中
					qu.offer(i);
				}
			}
		}
	}
	// 打印路径
	public static void printPath(int u){
		// 如果是-1代表到达起点
		if(path[u] == -1){
			System.out.print("路径："+u+"->");
		}else{
			// 上一层
			printPath(path[u]);
			// 递归结束，打印路径
			System.out.print(u+"->");
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();// 点数
		e = sc.nextInt();// 边数
		// 初始化
		G = new int[n + 1][n + 1];
		dis = new int[n + 1];
		path = new int[n + 1];
		// 路径长度初始化为-1，不仅可以代表源点到点i路径长度，还可以代表是否访问过
		for(int i = 0; i < dis.length; i++){
			dis[i] = -1;
		}
		// 输入边
		int u, v;
		for(int i = 0; i < e; i++){
			u = sc.nextInt();
			v = sc.nextInt();
			G[u][v] = 1; // 有向图
		}
		// 从源点1开始的路径
		Bfs(1);
		// 得到长度
		for(int i = 1; i <= n; i++){
			System.out.print("源点1到点"+i+"的长度："+dis[i]+",");
			// 打印路径
			printPath(i);
			System.out.println();
		}
		sc.close();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

2.输入的数据
6 8
1 2
1 3
2 6
3 4
3 5
3 6
4 5
4 6
3.对应的无权图

4.输出

5.对应的邻接表表现图

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class AdlistShoterPath {
	static int n;// 点数
	static int e;// 边数
	static ArrayList<Integer> G[];// 邻接表
	static int dis[];// 路径 dis[i] = j, 默认1到节点i最短路径j
	static int path[];// 记录路线
	
	// BFS最短路径
	public static void Bfs(int u){
		path[u] = -1;// 起点
		// 源点 初始化为访问过
		dis[u] = 0;
		Queue<Integer> qu = new LinkedList<Integer>();
		qu.offer(u);// 添加源点进入
		while(!qu.isEmpty()){
			u = qu.poll();
			// 以u点扩散，得到它的邻接表
			for(int i = 0; i < G[u].size(); i++){
				// 只需判断是否访问过即可
				if(dis[G[u].get(i)] == -1){
					// 更新路径
					dis[G[u].get(i)] = dis[u] + 1;
					// 记录路径
					path[G[u].get(i)] = u;
					qu.offer(G[u].get(i));
				}
			}
		}
	}
	// 打印路径
	public static void printPath(int u){
		// 如果是0代表到达起点
		if(path[u] == -1){
			System.out.print("路径："+u+"->");
		}else{
			// 上一层
			printPath(path[u]);
			// 递归结束，打印路径
			System.out.print(u+"->");
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		e = sc.nextInt();
		// 初始化
		G =  new ArrayList[n + 1];
		dis = new int[n + 1];
		path = new int[n + 1];
		for(int i = 0; i < G.length; i++){
			G[i] = new ArrayList<>();
		}
		// 路径初始化为-1
		for(int i = 0; i < dis.length; i++){
			dis[i] = -1;
		}
		// 输入边
		int u, v;
		for(int j = 0; j < e; j++){
			u = sc.nextInt();
			v = sc.nextInt();
			G[u].add(v);// 有向图的添加
		}
		// 从1开始的路径
		Bfs(1);
		// 得到长度
		for(int i = 1; i <= n; i++){
			System.out.print("源点1到点"+i+"的长度："+dis[i]+",");
			// 打印路径
			printPath(i);
			System.out.println();
		}
		sc.close();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80