最短路径（Dijstra and Floyd)

本文主要是介绍最短路径（Dijstra and Floyd)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最短路径（Dijstra and Floyd)

数据结构：邻接表

	private final int maxValue = Integer.MAX_VALUE;private int[][] matrix;public Graph(int v) {matrix = new int[v][v];for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix[i].length; j++) {matrix[i][j] = maxValue;}}}void addEdge(int s, int t, int w) {matrix[s][t] = w;}

Dijstra

图解就不写了，直接引用他人写好的，图解链接
测试数据 7 9 0 1 6 0 3 2 1 2 5 1 5 3 3 1 7 3 4 5 4 6 1 4 5 5 5 2 3
对应结果

	/*** 测试数据 7 9 0 1 6 0 3 2 1 2 5 1 5 3 3 1 7 3 4 5 4 6 1 4 5 5 5 2 3* * @param g 邻接矩阵* @param s 起点*/void dijstra(int[][] g, int s) {// 最短路径长度int[] shortest = new int[matrix.length];// 判断最短路径是否已经求出int[] visited = new int[matrix.length];// 初始化源节点shortest[s] = 0;visited[s] = 1;int count = visited.length - 1;// 每次循环都计算出到一个节点的最短路径，所以一共循环 n-1 次while (count-- > 0) {int min = Integer.MAX_VALUE;int index = -1;// 找出到未计算区域中距离已经计算区域最近的点，保存在index中for (int j = 0; j < matrix.length; j++) {// 已经求出最短路径的节点不需要再加入计算并判断加入节点后是否存在更短路径if (visited[j] == 0 && matrix[s][j] < min) {min = matrix[s][j];index = j;}}// 更新最短路径shortest[index] = min;visited[index] = 1;// 更新从index节点到其他节点的较短路径for (int j = 0; j < matrix.length; j++) {// 这里不要使用加法，改成减法，否则Integer.MAX_VALUE相加会溢出成负数if (visited[j] == 0&& matrix[s][index] < matrix[s][j] - matrix[index][j]) {matrix[s][j] = matrix[s][index] + matrix[index][j];}}}// 打印结果System.out.println("|------|----------|---------|");System.out.printf("|------source node:%3s------|\n", s);System.out.println("| node | shortest | visited |");System.out.println("|------|----------|---------|");for (int i = 0; i < shortest.length; i++) {System.out.printf("|%6s|%10s|%9s|\n", i, shortest[i],visited[i] == 1);}System.out.println("|------|----------|---------|");}
}

Floyd
核心：尝试将每个点作为中转站，看是否能够使得原本的距离变短
测试数据 7 9 0 1 6 0 3 2 1 2 5 1 5 3 3 1 7 3 4 5 4 6 1 4 5 5 5 2 3

void floyd(int[][] g) {/*** 使用减法避免溢出成负数（权值没有负数） * 记忆的时候还是记忆成 i->j (g[i][j]) 通过 k 中转是否可以减少距离 (里面2层通过最外面一层的进行中转) * 即 g[i][j] > g[i][k] + g[k][j]*/for (int k = 0; k < g.length; k++)for (int i = 0; i < g.length; i++)for (int j = 0; j < g.length; j++)if (g[i][j] - g[i][k] > g[k][j])g[i][j] = g[i][k] + g[k][j];// 输出结果for (int i = 0; i < g.length; i++) {for (int j = 0; j < g.length; j++) {if (g[i][j] == maxValue) {System.out.printf("%3s ", "∞");} else {System.out.printf("%3s ", g[i][j]);}}System.out.println();}}