单源最短路.ppt

单源最短路 单源最短路的两个算法（dijkstra，spfa） 李瑞杰 单源最短路（sssp） Dij（s） D【s】=True； D【other nodes】=False For k=1 to n-1 do select an K which D[k] has a smallest Edge[k] For each node j not in D relax(s,k,j) 热浪（USACO） 德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来不错，可是他们并不是很擅长生產富含奶油的乳製品。Farmer John此时以先天下之忧而忧，后天下之乐而乐的精神，身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。 FJ已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过T (1 = T = 2,500)个城镇，方便地标号為1到T。除了起点和终点外地每个城镇由两条双向道路连向至少两个其它地城镇。每条道路有一个通过费用（包括油费，过路费等等）。考虑这个有7个城镇的地图。城镇5是奶源，城镇4是终点（括号内的数字是道路的通过费用）。 　　　 [1]----1---[3]- 　　　　　　　　　　　　　　 /　　　　　　 \ 　　　　　　　　　　 [3]---6---[4]---3--[3]--4 　　　　　　　　　　 /　　　　　　 /　　 /| 　　　　　　　　　　5　　　　 --[3]-- --[2]- | 　　　　　　　　　　 \　　 /　　　　/　　 | 　　　　　　　　　　 [5]---7---[2]--2---[3]--- 　　　　　　　　　　　　　　|　　 / 　　　　　　　　　　　　 [1]------ 经过路线5-6-3-4总共要花费3 (5-6) + 4 (6-3) + 3 (3-4) = 10的费用。 给定一个地图，包含C (1 = C = 6,200)条直接连接2个城镇的道路。每条道路由道路的起点Rs，终点Re (1 = Rs = T; 1 = Re = T)，和花费(1 = Ci = 1,000)组成。求从起始的城镇Ts (1 = Ts = T)到终点的城镇Te(1 = Te = T)最小的总费用。 输入格式 Input Format * 第一行: 4个由空格隔开的整数: T, C, Ts, Te * 第2到第C+1行: 第i+1行描述第i条道路。有3个由空格隔开的整数: Rs, Re和Ci 输出格式 Output Format * 第一行: 一个单独的整数表示Ts到Te的最短路的长度。（不是费用麼？怎麼突然变直白了 ——译者注）数据保证至少存在一条道路。 样例输入 Sample Input 样例输出 Sample Output 7 11 5 4 7 2 4 2 时间限制 Time Limitation 1 4 3 各个测试点1s 7 2 2 3 4 3 5 7 5 7 3 3 6 1 1 6 3 4 2 4 3 5 6 3 7 2 1 这道题是一道比较简单的求单源最短路的问题 可以用dijkstra算法spfa算法等解决 可以用来练习熟悉一些最短路算法 SPFA算法 我们用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。我们采取的方法是动态逼近法： 设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。 SPFA算法 适用条件: 任意边权为实数的图 定理: 只要最短路径存在，上述SPFA算法必定能求出最小值。 证明：每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值d[v]变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结