一. 原题链接：http://poj.org/problem?id=2449
二. 题目大意：给一个有向图，给出S（起点）和T（终点），让你求第K短路。
三. 思路：启发式搜索A*算法+SPFA求最短路做为H[]估值函数。
先建立原图的反向图，用SPFA算法，求出图中各点到源点的最短路径。
A*算法有2个函数G(x)和H(x)，G(x)表示从起点到该点x的路径长度，H(x)表示从该点到终点的最短路径。
A*算法步骤：
1.计算起点的G(x)（也就是0）和H(x)，将其加入优先级队列（优先级队列优先级为G(x)+H(x)，小的话先出。）。
2.在优先级队列不为空时，一直弹出队首，对于每个队首元素，进行如下操作：
遍历与其连接的每个点，更新每个店的G(x)和H(x)，将其压入优先级队列。
3.当第k次寻找到终点，G(x)+H(x)的值就是第K短路的路径长度。
4.若未到第k次，队列就为空，说明不存在第K短路，输出-1。
利用优先队列维护，相当于A*算法中所谓开启列表，而这题没有关闭列表，因为要搜多条路径。
其实这题的A*算法说白了，就是在BFS的基础上，队列使用优先队列。再加上寻找到第K次才退出，总体难度还是不难，但是由于太久没做还有强行用Java的原因，做了一个晚上加上一个早上。
四.注意点:
1. 有重边，不要考虑邻接矩阵。
2. S==T的时候，先k++。因为当S==T的时候，要算先走一次。
五.代码:
//POJ2449 import java.util.*; class Main { final static int MAX_SIZE = 1010; final static int INF = 0x3f3f3f3f; static class Node{ public int v; public int weight; } static List<Node> Graph[] = new ArrayList[MAX_SIZE]; static List<Node> reGraph[] = new ArrayList[MAX_SIZE]; static int nodeNum; static int edgeNum; static int k; static int[] SPFA(int start, int end){ int dist[] = new int[nodeNum+1]; boolean inQue[] = new boolean[nodeNum+1]; Queue<Integer> que = new LinkedList<Integer>(); int i, cur; for (i = 0; i < nodeNum+1; i++){ dist[i] = INF; inQue[i] = false; } dist[start] = 0; que.offer(start); inQue[start] = true; while (!que.isEmpty()) { cur = que.poll(); inQue[cur] = false; Iterator<Node> it = reGraph[cur].iterator(); while (it.hasNext()){ Node node = it.next(); int v = node.v; int weight = node.weight; if (dist[v] > dist[cur] + weight){ dist[v] = dist[cur] + weight; if (!inQue[v]){ inQue[v] = true; que.offer(v); } } } } return dist; } static int AStar(int start, int end, int []H){ class Point{ public int id; public int h; public int g; } Comparator<Point> order = new Comparator<Point>(){ public int compare(Point a, Point b){ int fa = a.g + a.h; int fb = b.g + b.h; return fa>fb? 1:(fa==fb?0:-1); } }; Queue<Point> que = new PriorityQueue<Point>(nodeNum, order); Point cur = new Point(); cur.g = 0; cur.h = H[start]; cur.id = start; que.offer(cur); int cnt = 0; while(!que.isEmpty()){ cur = que.poll(); if (cur.id == end){ cnt++; if (cnt == k){ return cur.g + cur.h; } } Iterator<Node> it = Graph[cur.id].iterator(); while(it.hasNext()){ Node tmp = it.next(); int v = tmp.v; int weight = tmp.weight; Point nextP = new Point(); nextP.g = cur.g + weight; nextP.h = H[v]; nextP.id = v; que.offer(nextP); } } return -1; } public static void main(String[] args) { Scanner in = new Scanner(System.in); nodeNum = in.nextInt(); edgeNum = in.nextInt(); int u, v, w, i; for (i = 1; i <= nodeNum; i++) Graph[i] = new ArrayList<Node>(); for (i = 1; i <= nodeNum; i++) reGraph[i] = new ArrayList<Node>(); for (i = 0; i < edgeNum; i++){ u = in.nextInt(); v = in.nextInt(); w = in.nextInt(); Node newNode = new Node(); newNode.v = v; newNode.weight = w; Graph[u].add(newNode); //反向图 Node newNodeForRe = new Node(); newNodeForRe.v = u; newNodeForRe.weight = w; reGraph[v].add(newNodeForRe); } int start, end; start = in.nextInt(); end = in.nextInt(); k = in.nextInt(); int dist[] = SPFA(end, start); if (start == end) k++; System.out.println(AStar(start, end, dist)); in.close(); } }
