单源最短路径（java版）

📑前言

本文主要是【单源最短路径】——单源最短路径使用的文章，如果有什么需要改进的地方还请大佬指出??

🎬作者简介：大家好，我是听风与他🥇
??博客首页：CSDN主页听风与他
🌄每日一句：狠狠沉淀，顶峰相见

单源最短路径

• 以如下图为例

Dijkstra单源最短路径

package 图论;

import java.util.Arrays;
import java.util.Scanner;

public class Dijkstra {
/*
6 9
0 1 1
0 2 12
1 2 9
1 3 3
2 4 5
3 2 4
3 4 13
3 5 15
4 5 4
 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int vn=sc.nextInt();//顶点
		int en=sc.nextInt();//边
		int g[][]=new int[vn][vn];
		int dis[]=new int[vn];
		int vis[]=new int[vn];
		for(int i=0;i<vn;i++) {
			for(int j=0;j<vn;j++) {
				if(i==j) g[i][j]=0;
				else g[i][j]=999;
			}
		}
		for(int i=0;i<en;i++) g[sc.nextInt()][sc.nextInt()]=sc.nextInt();
		for(int i=0;i<vn;i++) {
			dis[i]=g[0][i];//初始化数组
		}
		vis[0]=1;//标记已经使用过了，松弛过了
		int mindex=0;//记录当前从v0到哪一个点的距离最小（未松弛过的点）
		for(int i=0;i<vn-1;i++) {
			int min=999;
			for(int j=0;j<vn;j++) {//dis数组里找最小的，未松弛过的点
				if (vis[j]==0 && dis[j]<min) {
					min=dis[j];//记录最小的距离
					mindex=j;//记录最小的顶点编号
				}
			}
			vis[mindex]=1;//通过这个点去松弛
			for(int j=0;j<vn;j++) {
				if(g[mindex][j]<999 && mindex!=j)
				dis[j]=Math.min(dis[j], dis[mindex]+g[mindex][j]);
			}
		}
		System.out.println(Arrays.toString(dis));
	}

}

Floyd单源最短路径

package 图论;

import java.util.Arrays;
import java.util.Scanner;

public class Floyd {
/*
4 8
0 1 2
1 2 3
0 2 6
2 0 7
0 3 4
3 0 5
2 3 1
3 2 12
 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		int[][] g=new int[n][n];
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(i==j) g[i][j]=0;
				else g[i][j]=999;
			}
		}
		for(int i=0;i<m;i++) {
			g[sc.nextInt()][sc.nextInt()]=sc.nextInt();
		}
		//弗洛伊德算法
		for(int k=0;k<n;k++) {
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					if(g[i][k]<999 && g[k][j]<999 && i!=j && i!=k && j!=k) {
						g[i][j]=Math.min(g[i][j], g[i][k]+g[k][j]);
					}
				}
			}
		}
		for(int[] x:g) {
			System.out.println(Arrays.toString(x));
		}
	}

}

打印结果

[0, 1, 8, 4, 13, 17]

📑文章末尾