不断的学习,我们才能不断的前进
一个好的程序员是那种过单行线马路都要往两边看的人

最短路径

从某个源点到其余各顶点

Dijkstra:
从某个源点 到 其余各点的最短路径:Dijkstra 算法
主要思想:以起始点为中心向外层层扩展,每次选择当前结点距离最短的那个结点,并重新计算更新距离,再次选择最短的。
采用的是邻接矩阵来表示图,主要步骤如下:

  1. 前提:
    需要一个数组distance来记录到其余顶点之间的最短路径;
    需要一个boolean数组visited来判断到该顶点是否已经找到最短路径
    需要一个二维数组path来判断到该顶点的最短路径 需要经过的顶点;
  2. 计算起始顶点V0,到其余各个顶点之间的距离
  3. 选择计算出来最短的距离的顶点,Vi。
  4. 以Vi为起始顶点,计算到其他顶点之间的距离,并更新记录距离的表(选择最短距离) 和 path 路径表。
  5. 重复步骤4,知道所有顶点都被访问

每一对顶点之间的最短路径

Floyd 算法:
主要思想是:
已知道两个顶点v,w之间的路径为distance[v][w], 而第三个顶点u,满足distance[v][u]+distance[u][w]< distance[v][w],所以
v,w之间的最短路径,更新为v,u,w。 依次类推

   1. 前提:
       一个二维矩阵distance 记录最开始两个顶点之间的距离;
       一个三维矩阵path,记录最短路径上的顶点。

java 代码

/**
 * 图的最短路径算法
 *
 */
public class ShortestPath {

	/**
	 * 从某个源点 到 其余各点的最短路径:Dijkstra 算法
	 * 主要思想:以起始点为中心向外层层扩展,每次选择当前结点距离最短的那个结点,并重新计算更新距离,再次选择最短的
	 * 采用的是邻接矩阵来表示图,主要步骤如下:
	 *  1. 前提:
	 *      需要一个数组distance来记录到其余顶点之间的最短路径;
	 *      需要一个boolean数组visited来判断到该顶点是否已经找到最短路径
	 *      需要一个二维数组path来判断到该顶点的最短路径 需要经过的顶点;
	 *  2. 计算起始顶点V0,到其余各个顶点之间的距离
	 *  3. 选择计算出来最短的距离的顶点,Vi。
	 *  4. 以Vi为起始顶点,计算到其他顶点之间的距离,并更新记录距离的表(选择最短距离) 和 path 路径表。
	 *  5. 重复步骤4,知道所有顶点都被访问
	 * @param matrix 邻接矩阵表示顶点和边
	 * @param start 表示开始的顶点
	 */
	public void ShortestPath_Dijkstra(int[][] matrix,int start) {
		int n = matrix.length;// 顶点的数量。
		boolean[] visited = new boolean[n]; // 表示n个顶点的最短距离是否被计算出来
		int[] distance = new int[n];// 用来记录开始顶点到各个顶点之间的最短距离
		boolean[][] path=new boolean[n][n]; // 二维数组记录 最短路径 经过的顶点。path[v][w]表示 从开始顶点到顶点v的最短路径包含顶点w

		for (int v = 0; v < n; v++) {
			distance[v] = matrix[start][v];
			if(distance[v]<Integer.MAX_VALUE){
				path[v][start]=true;
				path[v][v]=true;
			}
		}
		for (int i = 1; i < n; i++) { // 这一层循环表示需要查找的次数,每次都会找到一个最短路径
			int min = Integer.MAX_VALUE;// 当前离 开始结点最近的距离
			int v = 0;// 当前离 开始结点最近的距离 哪一个结点
			for (int w = 0; w < n; w++) {
				if (w != start && !visited[w]) { // 当前结点不是开始结点,而且最短距离没有计算出来
					if (distance[w] < min) {
						min = distance[w];
						v = w;
					}
				}
			}
			visited[v] = true;
			// 更新最短距离
			for (int w = 0; w < n; w++) {
				if (w != start && !visited[w] && (matrix[v][w]!=Integer.MAX_VALUE && min + matrix[v][w] < distance[w])) {
					distance[w] = min + matrix[v][w];
					System.arraycopy(path[v],0,path[w],0,n); //path[w]=path[v];
					path[w][w]=true;
				}
			}
		}
		for(int i=0;i<n;i++){
			if(i==start) continue;
			if(distance[i]==Integer.MAX_VALUE)System.out.println("从顶点"+start+"到顶点"+i+"的最短路径不存在");
			else {
				StringBuilder sb=new StringBuilder("从顶点"+start+"到顶点"+i+"的最短路径是"+distance[i]+" 包含的结点有:");
				for(int j=0;j<n;j++){
					if(path[i][j]) sb.append(j+" ");
				}
				System.out.println(sb.toString());
			}

		}

	}

	/**
	 * Floyd 算法生成每一对顶点之间的最短路径,
	 * 主要思想是:
	 *  已知道两个顶点v,w之间的路径为distance[v][w], 而第三个顶点u,满足distance[v][u]+distance[u][w]< distance[v][w],所以
	 *  v,w之间的最短路径,更新为v,u,w。 依次类推
	 *
	 *  1. 前提:
	 *      一个二维矩阵distance 记录最开始两个顶点之间的距离;
	 *      一个三维矩阵path,记录最短路径上的顶点。
	 *
	 * @param matrix
	 * @param start
	 */
	public void ShortestPath_FLOYD(int[][] matrix,int start, int end) {
		int n = matrix.length;// 顶点的数量。
		int[][] distance = new int[n][n];// 用来记录两个顶点之间的最短距离
		boolean[][][] path=new boolean[n][n][n]; // path[v][w][u] 为true 表示,u是从v 到 w 最短路径上的顶点

		for(int v=0;v<n;v++){
			for(int w=0;w<n;w++){
				distance[v][w]=matrix[v][w];
				if(distance[v][w]<Integer.MAX_VALUE){ // 表示 v 到 w 有直接路径可以访问
					path[v][w][v]=true;path[v][w][w]=true;
				}
			}
		}
		for(int u=0;u<n;u++){
			for(int v=0;v<n;v++){
				for(int w=0;w<n;w++){
					if(distance[v][u]!=Integer.MAX_VALUE && distance[u][w]!=Integer.MAX_VALUE && distance[v][u]+distance[u][w]< distance[v][w]){ // 表示从v 经过 u 在经过 w 是 更短的一条路径
						distance[v][w]=distance[v][u]+distance[u][w];
						for(int i=0;i<n;i++){ // 更新路径表 path
							path[v][w][i]=path[v][u][i] || path[u][w][i];
						}
					}
				}
			}
		}

		StringBuilder sb=new StringBuilder("从顶点"+start+"到顶点"+end+"的最短路径是"+distance[start][end]+" 包含的结点有:");
		for(int j=0;j<n;j++){
			if(path[start][end][j]) sb.append(j+" ");
		}
		System.out.println(sb.toString());

	}

	public static void main(String[] args) {
		int m=Integer.MAX_VALUE;
		int[][] matrix=new int[][]{{m,m,10,m,30,100},{m,m,5,m,m,m},{m,m,m,50,m,m},{m,m,m,m,m,10},{m,m,m,20,m,60},{m,m,m,m,m,m}};
		ShortestPath main=new ShortestPath();
		System.out.println("单源最短路径");
		main.ShortestPath_Dijkstra(matrix,0);
		System.out.println("ShortestPath_FLOYD:每对顶点直接的最短路径");
		main.ShortestPath_FLOYD(matrix,0,5);
	}
}

最小生成树

Prim 算法

基本思想有两个集合U,T,U表示已访问的结点,T表示未访问的结点; 从U 集合出发,选择到T未访问结点里面距离最小的结点 加入U,重复这个过程知道T 为空。
Prim 适合稠密图,时间复杂度为O(n2),与边无关,与顶点数量有关系。

克鲁斯卡尔算法

适合稀疏图的最小生成树算法。基本思想:
初始化T为空,T保存选择出的结点,把所有的边按从小到大进行排序,依次选择最小代价的边,如果选择这个边 两头的顶点在T 里面,则把这条边加入T中会构成一个环,所以抛弃这条边,继而选择下一个最小代价的边,直到所有的结点都被选择。

DEMO

package algorithm;

/**
 * @Author laijinhan
 * @date 2021/7/23 上午10:31
 */

import java.util.PriorityQueue;

/**
 * 最小生成树,来自牛客 : https://www.nowcoder.com/practice/735a34ff4672498b95660f43b7fcd628?tpId=190&&tqId=37981&rp=1&ru=/activity/oj&qru=/ta/job-code-high-rd/question-ranking
 */
public class Prim {
	/**
	 * 一个有n户人家的村庄,有m条路连接着。村里现在要修路,每条路都有一个代价,现在请你帮忙计算下,最少需要花费多少的代价,就能让这n户人家连接起来
	 * @param args: 3,3,[[1,3,3],[1,2,1],[2,3,1]]
	 */
	/**
	 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
	 *
	 * 返回最小的花费代价使得这n户人家连接起来
	 * @param n int n户人家的村庄
	 * @param m int m条路
	 * @param cost int二维数组 一维3个参数,表示连接1个村庄到另外1个村庄的花费的代价
	 * @return int
	 */
	public int miniSpanningTree_Prim (int n, int m, int[][] cost) {
		// 邻接矩阵表示 无向图
		int[][] graph=new int[n+1][n+1];// 下标0 不使用
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				graph[i][j] = Integer.MAX_VALUE;
			}
		}
		for(int[] edge:cost){
			if (graph[edge[0]][edge[1]] < Integer.MAX_VALUE) {
				if (graph[edge[0]][edge[1]] > edge[2]) {
					graph[edge[0]][edge[1]] = edge[2];
					graph[edge[1]][edge[0]] = edge[2];
				}
			} else {
				graph[edge[0]][edge[1]] = edge[2];
				graph[edge[1]][edge[0]] = edge[2];
			}
		}
		boolean[] visit=new boolean[n+1];// 表示当前结点是否访问
		int[] distance=new int[n+1]; // 表示每次需要选择的最小边
		visit[1]=true;// 从顶点1开始
		for(int i=1;i<=n;i++){
			distance[i]=graph[1][i];
		}
		int ans=0;
		for(int i=2;i<=n;i++){
			int min=Integer.MAX_VALUE;// 选择的最小边
			int next=-1;// 选择的最小遍对应的顶点
			for(int j=1;j<=n;j++){
				if (!visit[j] && distance[j] < min) {
					next = j;
					min = distance[j];
				}
			}
			ans+=min;
			visit[next]=true;
			// 更新distance
			for(int j=1;j<=n;j++){
				if (!visit[j] && distance[j] >graph[next][j]) {
					distance[j] = graph[next][j];
				}
			}
		}
		return ans;
	}

	/**
	 * 把边按照权值排序,每次选择最小权值的边,然后在判断是否会生成环
	 * @param n
	 * @param m
	 * @param cost
	 * @return
	 */
	public int miniSpanningTree_Kruskal (int n, int m, int[][] cost) {
		// 使用一个数组 father记录每个结点的父节点,来判断是否有环
		int[] father=new int[n+1];
		for(int i=0;i<=n;i++) father[i]=i;

		PriorityQueue<Edge> queue=new PriorityQueue<>((a,b)->(a.cost-b.cost));
		for(int[] cos:cost)queue.offer(new Edge(cos));
		int ans=0;
		while(!queue.isEmpty()){
			Edge poll = queue.poll();
			// 如果加入的边的两端结点 的父节点,不相同,说明不会产生环
			if(getFatherNode(father,poll.startNode)!=getFatherNode(father,poll.endNode)){
				ans+=poll.cost;
				union(father,poll.startNode,poll.endNode);// 两端结点 写入father数组,记录startNode的父节点为endNode
			}
		}
		return ans;
	}
	public void union(int[] f, int a ,int b){
		int fa = getFatherNode(f,a);
		int fb = getFatherNode(f,b);
		f[fa]=fb;
	}
	public int getFatherNode(int[] father,int index){
		if(father[index]==index) return index;
		father[index]=getFatherNode(father,father[index]);
		return father[index];
	}
	class Edge{
		int startNode;
		int endNode;
		int cost;
		Edge(int[] edges){
			this.startNode=edges[0];
			this.endNode=edges[1];
			this.cost=edges[2];
		}
	}
	public static void main(String[] args) {
		/**
		 * 假设G=(V,E)为一网图,其中V为顶点的集合,E为边的集合。从某一顶点u1出发,选择与它关联的具有最小权值的边(u1, v),将其顶点v加入到生成树顶点
		 *
		 * 集合U中。U用于存放G的最小生成树中的顶点,T存放G的最小生成树中的边
		 */
		System.out.println(new Prim().miniSpanningTree_Prim(3,3,new int[][]{{1,3,3},{1,2,1},{2,3,1}}));
	}
}


目录