程序员常用九大算法（二分查找（非递归）、分治、动态规划、KMP、贪心、普里姆、克鲁斯卡尔、迪杰斯特拉、弗洛伊德算法）_程序员常用的十大经典算法

程序员常用九大算法：

1.二分查找（非递归）
2.分治算法
3.动态规划算法
4.KMP算法
5.贪心算法
6.普里姆算法
7.克鲁斯卡尔算法
8.迪杰斯特拉算法
9.弗洛伊德算法

1.二分查找（非递归）：

就是不使用递归的二分查找，这里不做介绍

二分查找代码实现：

public class BinarySearchNoRecur {
	public static void main(String[] args) {
		int[] arr = { 1, 3, 8, 10, 11, 67, 100 };
		int i = binarySearch(arr, 11);
		System.out.println(i);
	}

	public static int binarySearch(int[] arr, int target) {
		int left = 0;
		int right = arr.length - 1;
		while (left <= right) {
			int mid = (left + right) / 2;
			if (arr[mid] == target) {
				return mid;
			} else if (arr[mid] > target) {
				right = mid - 1;

			} else {
				left = mid + 1;
			}
		}
		return -1;
	}
}

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

2.分治算法：

比起算法，更像是一种思维


分治算法应用场景：
汉诺塔：

问题分析：

汉诺塔代码实现：

public class Hanoitower {
	public static void main(String[] args) {
		hanoiTower(6, 'a', 'b', 'c');
	}

	public static void hanoiTower(int num, char a, char b, char c) {
		// 如果只有一个盘
		if (num == 1) {
			System.out.println("第1个盘从 " + a + "->" + c);
		} else {
			// 如果我们有n >= 2情况，我们总是可以看做是两个盘1.最下面一个盘2.上面的盘
			// 1.先把最上面的所有盘A -> B
			//将b参数和c参数互换，下一次递归的任务就是将a移动到b，而不会使用到c，c的使用在下下次递归中
			hanoiTower(num - 1, a, c, b);
			// 2.将最下面的盘A->C
			System.out.println("第" + num + "个盘从 " + a + "->" + c);
			// 3.把B塔的所有盘从B -> C,移动过程使用A塔
			hanoiTower(num - 1, b, a, c);

		}
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3.动态规划算法：

背包问题（0-1背包）：

思路分析和图解：

左表有基本信息，右表为最优解表

思路和公式：

背包问题代码实现（附讲解注释）：

import java.util.Arrays;

public class KnapsackProblem {
	public static void main(String[] args) {
		// 物品的重量
		int[] weight = { 1, 4, 3 };
		// 物品的价值
		int[] value = { 1500, 3000, 2000 };
		// 背包的容量
		int capacity = 4;
		// 物品的个数
		int num = weight.length;
		// 创建一个最优解数组（二维数组）
		// v[][]的每一个值都表示一种最优解
		// 例如：
		// v[2][3]表示：当容量为3时，只有前两种物品可选时存在的最优解
		// v[1][2]表示：当容量为2时，只有第一种物品可选时存在的最优解
		int[][] v = new int[num + 1][capacity + 1];

		// 为了记录放入商品的路径，定义一个二维数组
		//如果有新商品加入时，则对应商品数值置为1，否则不处理
		int[][] path = new int[num + 1][capacity + 1];

		// 初始化第一行和第一列，为0
		for (int i = 0; i < v.length; i++) {
			v[i][0] = 0;
		}
		for (int i = 0; i < v[0].length; i++) {
			v[0][i] = 0;
		}

		// 根据公式进行动态规划处理
		for (int i = 1; i < v.length; i++) {// 不处理第一行
			for (int j = 1; j < v[0].length; j++) {// 不处理第一列
				// 如果重量比容量大，则无法放入，最优解为之前的值
				//
				if (weight[i - 1] > j) {
					v[i][j] = v[i - 1][j];
				} else {
					// 如果容量足够，那么最优解可能有两种情况
					// 1.放入物品的价值 + 剩余空间的最优解
					// 2.即使能放入物品，但是最优解不比上次的最优解大
//					v[i][j] = Math.max(v[i - 1][j], value[i - 1] + v[i - 1][j - weight[i - 1]]);
					if (v[i - 1][j] < value[i - 1] + v[i - 1][j - weight[i - 1]]) {
						v[i][j] = value[i - 1] + v[i - 1][j - weight[i - 1]];
						path[i][j] = 1;
					} else {
						// 如果只是用之前的值替换，则表示没有出现最优解
						v[i][j] = v[i - 1][j];
					}
				}
			}
		}

		for (int[] i : v) {
			System.out.println(Arrays.toString(i));
		}
		for (int[] i : path) {
			System.out.println(Arrays.toString(i));
		}
		int i = path.length - 1;
		int j = path[0].length - 1;
		while (i > 0) {// 逆向遍历
			if (path[i][j] == 1) {
				System.out.printf("第%d个商品放入到背包\n", i);
				j -= weight[i - 1];
			}
			i--;
		}
	}
}

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

4.KMP算法：

参考资料：https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html

KMP算法代码实现：

public class Kmp {
	public static void main(String[] args) {
		String string1 = "BBC ABCDAB ABCDABCDABDE";
		String string2 = "ABCDABD";
		int[] next = kmpNext("ABCDABD");

		System.out.println(kmpSearch(string1, string2, next));
	}

	/**
	 * 
	 * @param str1 原字符串
	 * @param str2 子串
	 * @param next 部分匹配表，是子串对应的部分匹配表
	 * @return 如果是-1就是没有匹配到，否则返回第一个匹配的位置
	 */
	public static int kmpSearch(String str1, String str2, int[] next) {
		// 遍历
		for (int i = 0, j = 0; i < str1.length(); i++) {

			// KMP核心算法
			while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
				j = next[j - 1];
			}
			if (str1.charAt(i) == str2.charAt(j)) {
				j++;
			}
			if (j == str2.length()) {
				return i - j + 1;
			}
		}
		return -1;
	}

	// 获取到一个字符串的部分匹配值表
	public static int[] kmpNext(String dest) {
		// 创建一个next数组保存部分匹配值
		int[] next = new int[dest.length()];
		// 第一个肯定是0，因为长度为一，没有前缀和后缀
		next[0] = 0;// 如果字符串时长度为1部分匹配值就是0
		for (int i = 1, j = 0; i < dest.length(); i++) {

			// 当dest.chatAt(i) != dest.chatAt(j),我们需要从next[j-1]获取新的j
			// 直到发现有dest.chatAt(i) == dest.chatAt(j)时退出、
			// 要j大于0才走这里
			while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
				j = next[j - 1];
			}
			// 当dest.chatAt(i) == dest.chatAt(j)满足时，部分匹配值就是+1
			if (dest.charAt(i) == dest.charAt(j)) {
				j++;
			}
			next[i] = j;
		}

		return next;

	}

	// 暴力匹配
	public static int violenceMatch(String str1, String str2) {
		char[] s1 = str1.toCharArray();
		char[] s2 = str2.toCharArray();
		boolean flag = false;
		int s1len = s1.length;
		int s2len = s2.length;
		int i = 0;
		int j = 0;
		while (i < s1len && j < s2len) {
			if (s1[i] == s2[j]) {
				i++;
				j++;
			} else {
				i = i - (j - 1);
				j = 0;
			}
		}
		if (j == s2len) {
			return i - j;
		} else {
			return -1;
		}

	}
}
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
82
83
84
85

5.贪心算法：

贪心算法应用场景：

利用贪心算法解题代码：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class Greedy {
	public static void main(String[] args) {
		HashMap<String, HashSet<String>> broadcasts = new HashMap<String, HashSet<String>>();
		HashSet<String> hashset1 = new HashSet<String>();
		hashset1.add("北京");
		hashset1.add("上海");
		hashset1.add("天津");

		HashSet<String> hashset2 = new HashSet<String>();
		hashset2.add("北京");
		hashset2.add("广州");
		hashset2.add("深圳");

		HashSet<String> hashset3 = new HashSet<String>();
		hashset3.add("成都");
		hashset3.add("上海");
		hashset3.add("杭州");

		HashSet<String> hashset4 = new HashSet<String>();
		hashset4.add("天津");
		hashset4.add("上海");

		HashSet<String> hashset5 = new HashSet<String>();
		hashset5.add("杭州");
		hashset5.add("大连");

		broadcasts.put("K1", hashset1);
		broadcasts.put("K2", hashset2);
		broadcasts.put("K3", hashset3);
		broadcasts.put("K4", hashset4);
		broadcasts.put("K5", hashset5);

		// allAreas,如果覆盖到其中一个地区，就会移除地区，如果全覆盖，则为空
		HashSet<String> allAreas = new HashSet<String>();
		allAreas.add("北京");
		allAreas.add("上海");
		allAreas.add("天津");
		allAreas.add("杭州");
		allAreas.add("大连");
		allAreas.add("成都");
		allAreas.add("广州");
		allAreas.add("深圳");

		// 创建ArrayList，存放选择的电台集合
		ArrayList<String> selects = new ArrayList<String>();
		String maxKey = null;

		HashSet<String> tempSet = new HashSet<String>();
		
		
		while (allAreas.size() != 0) {

			
			maxKey = null;

			for (String key : broadcasts.keySet()) {
				tempSet.clear();
				HashSet<String> areas = broadcasts.get(key);
				tempSet.addAll(areas);

				// 求出交集
				tempSet.retainAll(allAreas);
				// 求交集后，如果大小大于0，则表示还能覆盖新的地区，如果不大于零，就没有必要加入
				//如果maxKey为空，则赋值当前的key
				//如果maxKey不为空，则保存的是上次的最大覆盖地区key
				//如果当前这个集合包含的未覆盖地区的数量，比maxKey指向的集合未覆盖的地区还多，就重置maxKey
				if (tempSet.size() > 0 && (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size())) {
					maxKey = key;
				}
			}
			if (maxKey != null) {
				//加入选择
				selects.add(maxKey);
				//移除已添加的地区
				allAreas.removeAll(broadcasts.get(maxKey));

			}
		}
		//当退出循环后，则就按照贪心算法得到一个解
		System.out.println(selects);

	}
}
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
82
83
84
85
86
87

6.普里姆算法：

普里姆算法应用场景：

利用普里姆算法解题代码：

import java.util.Arrays;

public class Prim {
	public static void main(String[] args) {
		char[] data = new char[] { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
		int verxs = data.length;

		int[][] weight = new int[][] { { 10000, 5, 7, 10000, 10000, 10000, 2 }, { 5, 10000, 10000, 9, 10000, 10000, 3 },
				{ 7, 10000, 10000, 10000, 8, 10000, 10000 }, { 10000, 9, 10000, 10000, 10000, 4, 10000 },
				{ 10000, 10000, 8, 10000, 10000, 5, 4 }, { 10000, 10000, 10000, 4, 5, 10000, 6 },
				{ 2, 3, 10000, 10000, 4, 6, 10000 } };

		MGraph mGraph = new MGraph(verxs);
		MinTree minTree = new MinTree();
		minTree.createGraph(mGraph, verxs, data, weight);
		minTree.showGaph(mGraph);
		minTree.prim(mGraph, 1);
	}
}

//创建最小生成树 -> 村庄的图
class MinTree {
	/**
	 * 
	 * @param graph  图对象
	 * @param verxs  图对应的顶点个数
	 * @param data   图的各个顶点的值
	 * @param weight 图的邻接矩阵
	 */
	public void createGraph(MGraph graph, int verxs, char data[], int[][] weight) {
		int i, j;
		for (i = 0; i < verxs; i++) {
			graph.data[i] = data[i];
			for (j = 0; j < verxs; j++) {
				graph.weight[i][j] = weight[i][j];
			}
		}
	}

	public void showGaph(MGraph graph) {
		for (int i = 0; i < graph.weight.length; i++) {
			System.out.println(Arrays.toString(graph.weight[i]));
		}
	}

	/**
	 * 
	 * @param graph 图
	 * @param value 表示从图的第一个顶点开始生成,就是起点的下标
	 */
	public void prim(MGraph graph, int value) {
		int[] visited = new int[graph.verxs];
		visited[value] = 1;

		int h1 = -1;
		int h2 = -1;
		int minWeight = 10000;
		for (int k = 1; k < graph.verxs; k++) {//因为有graph.verxs顶点，普利姆算法借宿后，有graph.verxs-1边

			// 这个是确定每一次生成的子图，和那个结点的距离最近
			// 以下的双重循环是为了遍历每一条边,i为起点的下标，j为终点的下标
			for (int i = 0; i < graph.verxs; i++) {// i结点表示被访问的结点
				for (int j = 0; j < graph.verxs; j++) {// j结点表示还没有访问过的结点
					//当然这样做有点冗余
					//这里需要过滤一下，i已访问，j未访问才是需要的
					//并在这些条件下挑出距离最小的那一个
					if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {
						// 替代minWeight
						minWeight = graph.weight[i][j];
						//记录下距离最小边的记录
						h1 = i;
						h2 = j;
					}
				}
			}
			// 找到一条边
			System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + ">权值：" + minWeight);
			visited[h2] = 1;
			// minWeight 重新设置为最大值10000
			minWeight = 10000;
		}

	}
}

class MGraph {
	int verxs;// 表示圆的结点个数
	char[] data;// 存放节点数据
	int[][] weight;// 存放边，就是我们的邻接矩阵

	public MGraph(int verxs) {
		this.verxs = verxs;
		data = new char[verxs];
		weight = new int[verxs][verxs];
	}
}
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

7.克鲁斯卡尔算法：

克鲁斯卡尔算法应用场景：

利用克鲁斯卡尔算法解题代码：

import java.util.Arrays;

public class Kruskal {

	public int edgeNum;// 边的个数
	public char[] vertexs;// 顶点数组
	public int[][] matrix;// 邻接矩阵

	public static final int INF = Integer.MAX_VALUE;

	public static void main(String[] args) {
		char[] vertexs = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
		int matrix[][] = {
				/* A *//* B *//* C *//* D *//* E *//* F *//* G */
				/* A */ { 0, 12, INF, INF, INF, 16, 14 }, /* B */ { 12, 0, 10, INF, INF, 7, INF },
				/* C */ { INF, 10, 0, 3, 5, 6, INF }, /* D */ { INF, INF, 3, 0, 4, INF, INF },
				/* E */ { INF, INF, 5, 4, 0, 2, 8 }, /* F */ { 16, 7, 6, INF, 2, 0, 9 },
				/* G */ { 14, INF, INF, INF, 8, 9, 0 } };
		Kruskal kruskal = new Kruskal(vertexs, matrix);
		kruskal.kruskal();
//		kruskal.print();

	}

	public Kruskal(char[] vertexs, int[][] matrix) {
		int vlen = vertexs.length;
		this.vertexs = new char[vlen];
		// 使用复制的方式
		this.vertexs = vertexs.clone();
		this.matrix = matrix.clone();

		for (int i = 0; i < matrix.length; i++) {
			for (int j = i + 1; j < matrix[0].length; j++) {
				if (matrix[i][j] != INF) {
					edgeNum++;
				}
			}
		}
	}

	public void print() {
		System.out.println("邻接矩阵:");
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[0].length; j++) {
				System.out.printf("%10d\t", matrix[i][j]);
			}
			System.out.println();
		}

	}

	public void sortEdges(EData[] edges) {
		for (int i = 0; i < edges.length - 1; i++) {
			for (int j = 0; j < edges.length - 1 - i; j++) {
				if (edges[j].weight > edges[j + 1].weight) {
					EData tempData = edges[j];
					edges[j] = edges[j + 1];
					edges[j + 1] = tempData;
				}

			}
		}
	}

	/**
	 * 
	 * @param ch
	 * @return 返回下标
	 */
	public int getPosition(char ch) {
		for (int i = 0; i < vertexs.length; i++) {
			if (vertexs[i] == ch) {
				return i;
			}
		}
		return -1;
	}

	/**
	 * 功能：获取图中的边， 通过matrix 邻接矩阵类获取
	 * 
	 * @return
	 */
	public EData[] getEdges() {
		int index = 0;
		EData[] edges = new EData[edgeNum];
		for (int i = 0; i < vertexs.length; i++) {
			for (int j = i + 1; j < vertexs.length; j++) {
				if (matrix[i][j] != INF) {
					edges[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]);

				}
			}
		}
		return edges;
	}

	/**
	 * 功能：获取下标 为 i 的顶点的终点，用于后面判断两个顶点的终点是否相同
	 * 
	 * @param ends：数组就是记录了各个顶点对应的终点是哪个，ends数组是在遍历过程中，逐步形成
	 * @param i：表示传入的顶点对应的下标
	 * @return 返回的就是下标为 i 的这个顶点对应的终点的下标
	 * 
	 */
	public int getEnd(int[] ends, int i) {
		while (ends[i] != 0) {
			i = ends[i];
		}
		System.out.println("End:"+Arrays.toString(ends));
		return i;
	}

	public void kruskal() {
		int index = 0;// 表示最后结果数组的索引
		int[] ends = new int[edgeNum];// 用于保存
		EData[] rets = new EData[edgeNum];
		EData[] edges = getEdges();
		sortEdges(edges);

		for (int i = 0; i < edgeNum; i++) {
			int p1 = getPosition(edges[i].start);
			int p2 = getPosition(edges[i].end);

			int m = getEnd(ends, p1);// m = 4
			int n = getEnd(ends, p2);// n = 5

			// 是否构成回路
			if (m != n) {
				ends[m] = n;
				rets[index++] = edges[i];
			}
		}
		for (int i = 0; i < index; i++) {
			System.out.println(rets[i]);
		}
	}

}

//创建边的类
class EData {
	char start;// 起点
	char end;// 终点
	int weight;// 权值

	public EData(char start, char end, int weight) {
		this.start = start;
		this.end = end;
		this.weight = weight;
	}

	@Override
	public String toString() {
		return "[EData <" + start + ", " + end + "> weight=" + weight + "]";
	}
}
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157

8.迪杰斯特拉算法：

迪杰斯特拉算法应用场景：

利用迪杰斯特拉算法解题代码：

import java.util.Arrays;

public class Dijkstra {
	public static void main(String[] args) {
		
		char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
		final int N = 65535;
		
		int[][] matrix = new int[][] { 
			{ N, 5, 7, N, N, N, 2 },
			{ 5, N, N, 9, N, N, 3 },
			{ 7, N, N, N, 8, N, N },
			{ N, 9, N, N, N, 4, N },
			{ N, N, 8, N, N, 5, 4 },
			{ N, N, N, 4, 5, N, 6 },
			{ 2, 3, N, N, 4, 6, N },
		};
		Graph graph = new Graph(vertex, matrix);
//		graph.showGraph();
		graph.dsj(6);
		graph.showDjs();

	}
}

class Graph {
	public char[] vertex;
	public int[][] matrix;
	// 已经访问的顶点的集合
	public VisitedVertex vv;

	public Graph(char[] vertex, int[][] matrix) {
		this.vertex = vertex;
		this.matrix = matrix;
	}

	public void showDjs() {
		vv.show();
	}

	public void showGraph() {
		for (int[] i : matrix) {
			System.out.println(Arrays.toString(i));
		}
	}

	/**
	 * 
	 * @param index 表示出发顶点对应的下标
	 */
	public void dsj(int index) {
		//新创建的已访问数组
		vv = new VisitedVertex(vertex.length, index);
		//首先更新一下起点
		update(index);
		for (int j = 1; j < vertex.length; j++) {
			index = vv.updateArr();
			update(index);
		}
	}

	// 更新index下标顶点到周围顶点的距离和周围顶点的前驱顶点
	public void update(int index) {
		int len = 0;
		// 根据遍历我们的邻接矩阵的 matrix[index]行
		for (int j = 0; j < matrix[index].length; j++) {
			// len含义是：出发顶点到index顶点的距离 + 从index顶点到j顶点的距离的和
			//一开始dis的值都是65535
			len = vv.getDis(index) + matrix[index][j];
			// 如果j没有被访问过，并且len小于出发顶点到j顶点的距离，就需要更新
			if (!vv.in(j) && len < vv.getDis(j)) {
				vv.updatePre(j, index);// 更新j顶点的前驱为index顶点
				vv.updateDis(j, len);// 更新出发顶点到j顶点的距离
			}

		}
	}

}

//已访问顶点的集合
class VisitedVertex {
	// 记录各个顶点是否访问过，1表示访问过，0表示未访问，会动态更新
	public int[] already_arr;
	// 每个小标对应的值为前一个顶点下标，会动态更新
	public int[] pre_visited;
//	记录出发顶点到其他所有顶点的距离，比如G为出发顶点，就会记录G到其他顶点的距离，会动态更新，求的最短距离就会存放到dis
	public int[] dis;

	/**
	 * 
	 * @param lenght 表示顶点的个数
	 * @param index  表示出发顶点对应的下标
	 */
	public VisitedVertex(int lenght, int index) {
		this.already_arr = new int[lenght];
		this.pre_visited = new int[lenght];
		this.dis = new int[lenght];

		// 初始化dis数组
		Arrays.fill(dis, 65535);
		// 设置出发顶点的访问距离为0
		this.dis[index] = 0;

		this.already_arr[index] = 1;
	}

	/**
	 * 功能：判断index顶点是否访问过
	 * 
	 * @param index
	 * @return 如果访问过，就放回true，否则返回false
	 */
	public boolean in(int index) {
		return already_arr[index] == 1;
	}

	/**
	 * 功能：更新出发顶点到index顶点的距离
	 * 
	 * @param index
	 * @param len
	 */
	public void updateDis(int index, int len) {
		dis[index] = len;
	}

	/**
	 * 功能：更新顶点的前驱为index结点
	 * 
	 * @param pre
	 * @param index
	 */
	public void updatePre(int pre, int index) {
		pre_visited[pre] = index;
	}

	/**
	 * 功能：返回出发顶点到index顶点的距离
	 * 
	 * @param index
	 */
	public int getDis(int index) {
		return dis[index];
	}

	/**
	 * 继续选择并返回新的访问顶点，比如这里的G，就是A点作为新的访问顶点（不是出发点）
	 * 
	 * @return
	 */
	public int updateArr() {
		int min = 65535, index = 0;
		for (int i = 0; i < already_arr.length; i++) {
			if (already_arr[i] == 0 && dis[i] < min) {
				min = dis[i];
				index = i;
			}
		}
		already_arr[index] = 1;
		return index;
	}

	public void show() {
		char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'D', 'G' };
		int count = 0;
		for (int i : dis) {
			if (i != 65535) {
				System.out.print(vertex[count++] + "(" + i + ")");
			}
		}
	}

}

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175

9.弗洛伊德算法：

弗洛伊德算法应用场景：

利用弗洛伊德算法解题代码：

import java.util.Arrays;

public class Floyd {
	public static void main(String[] args) {
		char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
		int[][] matrix = new int[vertex.length][vertex.length];
		final int N = 65535;
		matrix[0] = new int[] { 0, 5, 7, N, N, N, 2 };
		matrix[1] = new int[] { 5, 0, N, 9, N, N, 3 };
		matrix[2] = new int[] { 7, N, 0, N, 8, N, N };
		matrix[3] = new int[] { N, 9, N, 0, N, 4, N };
		matrix[4] = new int[] { N, N, 8, N, 0, 5, 4 };
		matrix[5] = new int[] { N, N, N, 4, 5, 0, 6 };
		matrix[6] = new int[] { 2, 3, N, N, 4, 6, 0 };

		Graph2 graph = new Graph2(vertex.length, matrix, vertex);
		graph.floyd();
		graph.show();
	}
}

class Graph2 {
	public char[] vertex;// 存放顶点
	public int[][] dis;// 保存，从各个顶点出发到其他顶点的距离，最后的结构，也是保存在该数组
	public int[][] pre;// 前驱

	public Graph2(int length, int[][] matrix, char[] vertex) {
		this.vertex = vertex;
		this.dis = matrix;
		this.pre = new int[length][length];
		// 对pre数组初始化
		// 一开始前驱是本身
		for (int i = 0; i < length; i++) {
			Arrays.fill(pre[i], i);
		}
	}

	public void show() {
		char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
		for (int k = 0; k < dis.length; k++) {

			for (int i = 0; i < dis.length; i++) {
				System.out.print(vertex[pre[k][i]] + " ");
			}
			System.out.println();
			for (int i = 0; i < dis.length; i++) {
				System.out.print("(" + vertex[k] + "到" + vertex[i] + "的最短路径是" + dis[k][i] + ")");
			}
			System.out.println();
			System.out.println();
		}
	}

	public void floyd() {
		int len = 0;
		// 从中间顶点的遍历
		for (int k = 0; k < dis.length; k++) {
			// 从i顶点出发a、b、c、d、。。。
			for (int i = 0; i < dis.length; i++) {
				for (int j = 0; j < dis.length; j++) {
					len = dis[i][k] + dis[k][j];// 求出i顶点出发，经过k中间点，到达j顶点距离
					if (len < dis[i][j]) {// 如果小于直连距离
						dis[i][j] = len;
						pre[i][j] = pre[k][j];
					}
				}
			}
		}
	}
}
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