最短路径

floyd

Dijkstra算法（单源最短路径）

使用dis[n]记录当前点到各个点的距离
使用book[n]区分已访问的点和未访问的点

//Dijkstra核心语句
		//选取最小值
		int minindex = 0;
		for(int i=1;i<=n-1;i++) {
			int min = 9999999;
			for(int j=1;j<=n;j++) {
				if(book[j]==0 && dis[j]<min) {
					min=dis[j];
					minindex = j;
				}
			}
			book[minindex] = 1;
			//更新dis[]
			for(int k=1;k<=n;k++) {
				if(edges[minindex][k]<9999999) {
					if(dis[k]>dis[minindex]+edges[minindex][k]) {
						dis[k]=dis[minindex]+edges[minindex][k];
					}
				}
			}
		}

完整代码

package lanqiao;

import java.util.Scanner;

public class Dijkstra {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//读入n是顶点个数，m是边数
		int n = sc.nextInt();
		int m = sc.nextInt();
		//初始化边
		int[][] edges = new int[n+1][n+1];
		for(int i=1;i<n;i++) {
			for(int j=1;j<n;j++) {
				if(i==j)edges[i][j] = 0;
				else edges[i][j] = 9999999;
			}
		}
		int[] dis = new int[n];
		int[] book = new int[n];
		//读入边
		for(int i=1;i<=m;i++) {
			int start = sc.nextInt();
			int end = sc.nextInt();
			int length = sc.nextInt();
			edges[start][end] = length;
		}
		//初始化dis数组，记录1号顶点到其余各个顶点的距离
		for(int i=1;i<=n;i++) {
			dis[i] = edges[1][i];
		}
		for(int i=1;i<=n;i++)
			book[i] = 0;
		book[1] = 1;
		//Dijkstra核心语句
		int minindex = 0;
		//循环n-1次，每次确定一个点
		for(int i=1;i<=n-1;i++) {
			int min = 9999999;
			for(int j=1;j<=n;j++) {
				if(book[j]==0 && dis[j]<min) {
					min=dis[j];
					minindex = j;
				}
			}
			book[minindex] = 1;
			for(int k=1;k<=n;k++) {
				if(edges[minindex][k]<9999999) {
					if(dis[k]>dis[minindex]+edges[minindex][k]) {
						dis[k]=dis[minindex]+edges[minindex][k];
					}
				}
			}
		}
		//输出结果
		for(int i=1;i<=n;i++) {
			System.out.print(dis[i]);
		}
	}
}