单源路径算法（Dijkstra、Bellman Ford）（Java邻接表、邻接矩阵、类实现）

单源路径算法（Dijkstra、Bellman Ford）（Java邻接表、邻接矩阵、类实现）

文章目录

• 单源路径算法（Dijkstra、Bellman Ford）（Java邻接表、邻接矩阵、类实现）
• 前言
• 一、邻接矩阵、邻接表、类如何实现？
• 二、Dijkstra、Bellman Ford
• • 1.Dijkstra_邻接矩阵实现
  • 2.Dijkstra_邻接表实现
  • 3.Bellman_Ford_类实现
• 总结

---

前言

默认大家已经了解图的基本术语，顶点、边、度等。

一、邻接矩阵、邻接表、类如何实现？

邻接矩阵
使用一个二维数组表示，若顶点为N，则创建一个N*N数组。
如果图的弧有权值，用无穷大表示顶点之间无边，用权值表示顶点之间有边，同一点之间的权值为0。如下图所示，该方法较为简单，不再赘述。

邻接表
如果图结构本身需要在解决问题的过程中动态地产生，则每增加或者删除一个顶点都需要改变邻接矩阵的大小，显然这样做的效率很低。除此之外，邻接矩阵所占用的存储单元数目至于图中的顶点的个数有关，而与边或弧的数目无关，若图是一个稀疏图的话，必然造成存储空间的浪费。邻接表很好地解决了这些问题。邻接表的存储方式是一种顺序存储与链式存储相结合的存储方式，顺序存储部分用来保存图中的顶点信息，链式存储部分用来保存图中边或弧的信息。

类

class Edge {
	int a, b, c;
	public Edge(int a, int b, int c) {
		this.a = a;
		this.b = b;
		this.c = c;
	}
}

a代表入边，b代表出边，c代表该边的权值。

接下来以代码来展示存储方法。

二、Dijkstra、Bellman Ford 1.Dijkstra_邻接矩阵实现

代码如下（示例）：

import java.util.Arrays;
import java.util.Iterator;

public class Dijkstra_matrix {
	
	public static void main(String[] args) {
		int INF=0x3f3f3f3f;
		int N = 5;
		int[] dist = new int[N+1];
		int[][] g = new int[N+1][N+1];
		boolean[] vis = new boolean[N+1];
		int[][] edges = { { 1, 2, 4 }, { 2, 3, 3 }, { 1, 3, 2 }, { 3, 4, 5 }, { 4, 5, 6 } };
		for(int i=0;i<N+1;i++) {
			for(int j=0;j<N+1;j++) {
				g[i][j] = INF;
			}
		}
		dist[1]=0;
		for(int i=2;i<N+1;i++) {	
			dist[i] = INF;
		}
		for (int i = 0; i < 5; i++) {
			int u = edges[i][0];
			int v = edges[i][1];
			int c = edges[i][2];
			g[u][v] = c;
		}
		dijkstra(dist,g,vis,N);
		System.out.println(dist[5]);
		
	}
	public static void dijkstra(int[] dist, int[][] g, boolean[] vis,int N)
	{
		int INF=0x3f3f3f3f;
	    for(int i=1;i<=N;i++)
	    {
	        int mark=-1,mindis=INF;
	        for(int j=1;j<=N;j++)
	        {
	            if(!vis[j]&&dist[j]<mindis)
	            {
	                mindis=dist[j];
	                mark=j;
	            }
	        }
	        vis[mark]=true;
	        System.out.println("mark:"+mark);
	        for(int j=1;j<=N;j++)
	        {
	            if(!vis[j])
	            {
	                dist[j]=Math.min(dist[j],dist[mark]+g[mark][j]);
	                System.out.println("g:"+g[mark][j]);
	            }
	        }
	    }
	}
}

2.Dijkstra_邻接表实现

代码如下（示例）：

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;


public class Dijkstra_adjacency_list {
	
	public static void main(String[] args) {
		int INF=0x3f3f3f3f;
		int N = 5;
		boolean[] vis = new boolean[N+1];
		int[][] edges = { { 1, 2, 4 }, { 2, 3, 3 }, { 1, 3, 2 }, { 3, 4, 5 }, { 4, 5, 6 } };
	
		// 建图 - 邻接表
	    Map<Integer, Map<Integer, Integer>> mp = new HashMap<>();
	    for (int i = 0; i < 5; i++) {
			int u = edges[i][0];
			int v = edges[i][1];
			int c = edges[i][2];
			if (!mp.containsKey(u))
	            mp.put(u, new HashMap<>());
	        mp.get(u).put(v, c);
		}
	    // 记录结点最早收到信号的时间 
	    int[] r = new int[N + 1];
	    for (int i = 1; i <= N; ++i)
	        r[i] = INF;
	    
	    //初始设置0
	    r[1] = 0;

	    // 记录已经找到最短路的结点
	    Set<Integer> s = new HashSet<>();

	    while (true) {
	        // 待查集中查找最近结点
	        int cur = -1, tim = INF;
	        for (int i = 1; i <= N; ++i) {
	            if (r[i] < tim && !s.contains(i)) {
	                cur = i;
	                tim = r[i];
	            }
	        }
	        if (cur == -1)
	            break;

	        // 将最近结点加入已查集合并更新
	        s.add(cur);
	        if (mp.containsKey(cur)) {
	            for (int v : mp.get(cur).keySet()) {
	                r[v] = Math.min(r[v], mp.get(cur).get(v) + tim);
	            }
	        }
	    }

	    int minT = -1;
	    //r[i]代表顶点1到顶点N的距离
	    for (int i = 1; i <= N; ++i)
	        minT = Math.max(minT, r[i]);
	    System.out.println(minT == INF ? -1 : minT); 
		
		
	}
	
}

3.Bellman_Ford_类实现

package Shortest_Path;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Edge {
	int a, b, c;

	public Edge(int a, int b, int c) {
		this.a = a;
		this.b = b;
		this.c = c;
	}

}

public class Bellman_Ford_class {
	public static void main(String[] args) {
		int N = 110, M = 6010;
		// dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y
		int[] dist = new int[N];
		int INF = 0x3f3f3f3f;
		int n, m, k;
		// 使用类进行存边
		n = 5;
		m = 3;
		k = 2;
		List<Edge> es = new ArrayList<>();
		int[][] times = { { 2, 1, 1 }, { 2, 3, 1 }, { 3, 4, 1 } };
		for (int i = 0; i < 3; i++) {
			int u = times[i][0];
			int v = times[i][1];
			int c = times[i][2];
			Edge e = new Edge(u, v, c);
			es.add(e);
		}
		// 最短路
		bf(dist,es,n,k);
		// 遍历答案
		int ans = 0;
		for (int i = 1; i <= n; i++) {
			System.out.println(dist[i]);
			ans = Math.max(ans, dist[i]);
		}
		System.out.println(ans > INF / 2 ? -1 : ans);
	}

	

	public static void bf(int[] dist, List<Edge> es,int n,int k) {
		int INF = 0x3f3f3f3f;
		// 起始先将所有的点标记为「距离为正无穷」
		Arrays.fill(dist, INF);
		// 只有起点最短距离为 0
		dist[k] = 0;
		// 迭代 n 次
		for (int p = 1; p <= n; p++) {
			int[] prev = dist.clone();
			// 每次都使用上一次迭代的结果，执行松弛 *** 作
			for (Edge e : es) {
				int a = e.a, b = e.b, c = e.c;
				dist[b] = Math.min(dist[b], prev[a] + c);
			}
		}
	}


}

---

总结

以上就是今天要讲的内容，Bellman_Ford可以实现负权值的单源路径查找。