最短路算法

Dijkstra

主要是解决图中一点到其余各点的距离
思路：
就是设两个集合，一个s，一个u，先将起点加入s集合，然后更新s集合到u集合的最短距离

然后再每次从u集合找到一个离s集合最近的点，将其加入s集合，再次更新所有的点

java
public static int[] dijkstar(int[][] graph,int startPoint){
		// 首先需要起始点到其他点的最短距离
		int[] dist = new int[graph.length];
		// 已经求出最短路径的点的集合
		boolean[] s = new boolean[graph.length];
		for(int i = 0;i<graph.length;i++) {
			if (i==startPoint) {
				s[i] = true;
			}else {
				s[i] = false;
			}
			dist[i] = graph[startPoint][i];
		}
		
		// 求到每个点的最短距离
		for(int i = 0;i<graph.length;i++) {
			int max = Integer.MIN_VALUE;
			int index = 0;
			for(int j = 0;j<graph.length;j++) {
				// 如果没在s集合，就找下一个加入s节点的
				if(!s[j]&&dist[j]<max) {
					max = dist[j];
					index = j;
				}
			}
			// 将该点加入s集合
			// index为当前要加入s的点
			s[index] = true;
			
			// 更新起点到其它点的距离
			for(int j = 0;j < graph.length;j++) {
				if(dist[j] > dist[index] + graph[index][j]) {
					dist[j] = dist[index] + graph[index][j];
				}
			}
			
			
		}
		
		return dist;
	}
	

floyd

求每对点之间的最短距离

有图G=(V,E)采用邻接矩阵cost存储，另外设置一个二维数组A用来存放当前顶点之间的最短路径长度，Floyd算法的基本思想是递推产生一个矩阵序列A0，A1，...,Ak,...An,其中Ak[i][j]表示从顶点i到顶点j的路径上经过的顶点编号不大于k的最短路径长度

简单来说，就是不断的修改路径的邻接矩阵，以某个节点为中转，修改到其他节点的最短路径

java
public static void floyd(int[][] graph) {
		
		for(int i = 0;i < graph.length;i++) {
			for(int j = 0;j<graph.length;j++) {
				// i是中转点
				for(int k = 0;k<graph.length;k++) {
					// 如果b-c + c-d 的距离小于 b-d
					if(graph[j][i] + graph[i][k] < graph[j][k]) {
						//更新b-d的距离
						graph[j][k] = graph[j][i] + graph[i][k];
					}
				}
				
			}
		}
	}