最短路专辑

Dijkstra

三步：

1 初始化 dist[] s[]

2 选出不在s[]中的最近的u

3 更新不在s[]中的dist

//朴素版	
public static int dijkstra(int[][] cost, int start, int end) {
		int[] dist = new int[n + 1], a = new int[n + 1];
		int min, u;
		for (int i = 1; i <= n; ++i) {
			dist[i] = cost[start][i];
			a[i] = 0;
		}
		a[start] = 1;
		for (int i = 0; i < n - 1; ++i) {
			min = INF;
			u = -1;
			for (int j = 1; j <= n; ++j) {
				if (dist[j] < min && a[j] == 0) {
					min = dist[j];
					u = j;
				}
			}
			if (u != -1) {
				a[u] = 1;
				for (int j = 1; j <= n; ++j) {
					if (a[j] == 0 && dist[j] > dist[u] + cost[u][j]
							&& cost[u][j] != INF) {
						dist[j] = dist[u] + cost[u][j];
					}
				}
			}
		}
		return dist[end];
	}

//优先队列优化版
public static class Node implements Comparable{
		int id, dist;
		public Node (int id, int dist) {
			this.id= id;
			this.dist = dist;
		}
		@Override
		public int compareTo(Object arg0) {
			int temp = ((Node)arg0).dist;
			if(this.dist<temp)
				return -1;
			if(this.dist>temp)
				return 1;
			return 0;
		}
		
	}
	
	public static int dijkstra(int[][] cost, int start, int end) {
		PriorityQueue<Node> pq = new PriorityQueue<Node>();
		int[] mark = new int[n+1], dist = new int[n+1];
		int update = 0;
		for(int i=1; i<=n; ++i) {
			dist[i] = INF;
			mark[i] = 0;
		}
		dist[start] = 0;
		pq.offer(new Node(start, 0));
		while(!pq.isEmpty() && update<n) {
			Node cur = pq.poll();
			if(mark[cur.id]==0) {
				update++;
				mark[cur.id] = 1;
				for(int i=1; i<=n; ++i) {
					if(cost[cur.id][i]!=INF && cur.dist+cost[cur.id][i]<dist[i]) {
						dist[i]= cur.dist+cost[cur.id][i];
						pq.offer(new Node(i, dist[i]));
					}
				}
			}
		}
		return dist[end];
	}

BellmanFord

三步：

1 初始化

2 对n-1个点，每条边做一次松弛（两个for）

3 再对每条边松弛，判断有无负环

FloyedWarshall

3个for

---

1 http://acm.hdu.edu.cn/showproblem.php?pid=2544 最短路

赤裸裸的最短路

2 http://acm.tju.edu.cn/toj/showp2870.html The K-th City

第k个进入s集合的顶点就是第k个最近点

3 http://acm.hdu.edu.cn/showproblem.php?pid=2066 一个人的旅行

多起点，多终点，但只要求出其中最短一条，通过设虚拟起点和虚拟终点（到每个起点和终点的距离为0）将复杂度降为（1000+s）*（1000+d）；

4 http://acm.hdu.edu.cn/showproblem.php?pid=1874 畅通工程续

赤裸裸的最短路

5 http://acm.hdu.edu.cn/showproblem.php?pid=2112 HDU Today

我是用了map把站名改成int，其次这里有起始点和终点一样的测试数据，要出0（个人觉得这个没什么必要。。。）

6 http://acm.hdu.edu.cn/showproblem.php?pid=1217 Arbitrage

http://acm.pku.edu.cn/JudgeOnline/problem?id=2240 Arbitrage

套汇问题，算法导论中有提到，我用floyed 求最大路，初始化时cost要初始成-1

7 http://acm.hdu.edu.cn/showproblem.php?pid=2680 Choose the best route

多起点，单终点。只是数据规模有点大，java要StreamTokenizer PrintWriter

8 http://acm.hdu.edu.cn/showproblem.php?pid=1690 Bus System

关键是构图，起始和终止点给出时是按第几个给出的，不是站点（这个问题我纠结好久），另外要64位（java long，不能用double代替）,dijkstra 和 floyed 都ac了，因为这里m>n 所以floyed 快些；

9 http://acm.hdu.edu.cn/showproblem.php?pid=1596 find the safest road

bellmanford 变形 把+变为*，说明一点 bellman的第三步判负环这里可以不写，因为边是0——1的乘下肯定更小，这样可以节省点时间

10 http://acm.hdu.edu.cn/showproblem.php?pid=1385 Minimum Transport Cost

这题关键是路径字典序，floyed路径初始化时初始化顶点号，在dp时对相等的判断，若路径可以更小取之

11 http://acm.hdu.edu.cn/showproblem.php?pid=2923 Einbahnstrasse

map+floyed ，有重边

12 http://acm.hdu.edu.cn/showproblem.php?pid=2962 Trucking

二分+最短路，二分时要将此状态时最高点最短路保存

13 http://acm.hdu.edu.cn/showproblem.php?pid=2722 Here We Go(relians) Again

难在读题，和构图，最短路还是裸的