import java.util.PriorityQueue; public class Dijkstra { /** * 1.假设带权有向图G的顶点集合为V,起始点为V0。 * 2.初始S={V0},T=V-S={其余顶点},其中集合S表示已经计算出最短距离的顶点,T是还没计算的剩余顶点。 * 3.初始化V0到其余各点的距离,D(V0,Vi)代表V0到Vi的最短距离,按如下规则。 * 3.若V0可以直接到达某个顶点Vi,则将边的权值赋给(V0,Vi),否则D(V0,Vi)=∞。 * 5.从T中选取一个与S中顶点有关联(直接相连)且权值最小的顶点W(这里用到了贪心法思想),加入到S中。 * 6.以W作为中间点,若V0到T中某个顶点Vi距离变短,则修改D(V0,Vi)的值。 * 7.重复5)和6)直到T为空。 * * @param src * @param dst * @param graph * @param n * @return */ public static int dijkstra(int src, int dst, int[][] graph, int n) { // 排序队列 PriorityQueue<Node> pNodes = new PriorityQueue<>(); int[] visitLog = new int[n + 1]; // 记录访问过的点 pNodes.add(new Node(src, 0)); while (!pNodes.isEmpty()) { Node tNode = pNodes.poll(); // 由于已经排序了 直接返回的就是最短路径 if (tNode.node == dst) { return tNode.cost; } if (visitLog[tNode.node] == 1) { continue; } visitLog[tNode.node] = 1; for (int i = 0; i < n; i++) { // 可联通且没有遍历过 if (graph[tNode.node][i] < 1000 && visitLog[i] != 1) { pNodes.add(new Node(i, tNode.cost + graph[tNode.node][i])); } } } return -1; } public static void main(String[] args) { int graph[][] = { { 0, 2, 3, 6, 1000, 1000 }, { 2, 0, 1000, 1000, 4, 6 }, { 3, 1000, 0, 2, 1000, 1000 }, { 6, 1000, 2, 0, 1, 3 }, { 1000, 4, 1000, 1, 0, 1000 }, { 1000, 6, 1000, 3, 1000, 0 } };// 地图 System.out.println(Dijkstra.dijkstra(0, 3, graph, 6)); System.out.println(Floyd.floyd(0, 3, graph, 6)); } } /** * * @author shichaopeng * * * * 邻接矩阵graph储存路径,同时最终状态代表点点的最短路径。如果没有直接相连的两点那么默认为一个很大的值(不要溢出)!而自己的长度为0. * 从第1个到第n个点依次加入图中。每个点加入进行试探是否有路径长度被更改。 * 而上述试探具体方法为遍历图中每一个点(i,j双重循环),判断每一个点对距离是否因为加入的点而发生最小距离变化。如果发生改变,那么两点(i,j)距离就更改。 * 重复上述直到最后插点试探完成。 * * 状态转移方程为: dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]) * 其中dp[x][y]的意思可以理解为x到y的最短路径。所以dp[i][k]的意思可以理解为i到k的最短路径dp[k][j]的意思可以理解为k到j的最短路径. */ class Floyd { /** * * @param src * @param dst * @param graph * @param n * @return */ public static int floyd(int src, int dst, int[][] graph, int n) { int[][] r = new int[n][n]; for (int i = 0; i < r.length; i++) { for (int j = 0; j < r.length; j++) { r[i][j] = graph[i][j]; } } for (int k = 0; k < n; k++) { // 任意2点插入点 让后动态规划 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { r[i][j] = Math.min(r[i][j], graph[i][k] + graph[k][j]); } } } return r[src][dst]; } } class Node implements Comparable<Node> { public int node; public int cost; public Node(int node, int cost) { super(); this.node = node; this.cost = cost; } @Override public int compareTo(Node o) { return cost - o.cost; } }