最短路径算法

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;
	}

}