网站域名和网址,程序开发过程的四个步骤,东阳住房和城市建设网站,音乐视频怎么做mp3下载网站参考图论算法#xff08;二#xff09;-最短路径的Dijkstra [ 单源 ] 和Floyd[ 多源 ] 解法#xff08;JAVA #xff09;这种算法也叫Floyd-Warshell算法#xff0c;虽然和Warshell算法名字相近#xff0c;算法思想也相近#xff0c;但确实是两种算法。对于一个带权图二-最短路径的Dijkstra [ 单源 ] 和Floyd[ 多源 ] 解法JAVA
这种算法也叫Floyd-Warshell算法虽然和Warshell算法名字相近算法思想也相近但确实是两种算法。对于一个带权图无向或有向全源最短路径问题就是找出每个顶点到其他所有顶点之间的最短距离。我们用一个n阶距离矩阵来记录最短路径的长度。需要注意的是该算法不适合带负权的回路图。
那么对于任意i到j的路径可以表示为vi, 顶点标号不大于k的一个中间顶点集vj
我们在把这种路径分成两个不相交的情况
情况一子集中不将第k个顶点作为中间顶点。在这种情况下路径所包含的中间顶点的编号都不大于k-1
情况二子集中不将第k个顶点作为中间顶点。在这种情况下顶点vk在中间顶点中且出现过一次。
上述两种情况可以由下图表示下面是一个实例用来展示算法的过程Input:
4 51 3 32 1 23 2 74 1 6
3 4 1
Output:
0 10 3 4 2 0 5 6 7 7 0 1 6 16 9 0
完整代码如下import java.util.Scanner;public class minPath {static int[][] e new int[10][10];static int n, m;static Scanner input new Scanner(System.in);public static void main(String[] args) {n input.nextInt();m input.nextInt();for (int i 1; i n; i) {for (int j 1; j m; j) {if (i j) {e[i][j] 0;} else {e[i][j] 99999999;}}}for (int i 1; i m; i) {int a input.nextInt();int b input.nextInt();int c input.nextInt();e[a][b] c;}floyd();for (int i 1; i n; i) {for (int j 1; j n; j) {System.out.print(e[i][j] );}System.out.println();}}public static void floyd() {for (int k 1; k n; k) {for (int i 1; i n; i) {for (int j 1; j n; j) {if (e[i][j] e[i][k] e[k][j]) {e[i][j] e[i][k] e[k][j];}}}}}
}
