【ACM】 最短路径算法

---

·（ 整理的并不完善）
·（就是手痒想写点东西）
·（顺便熟悉一下MarkDown基础语法）
· 模版代码
· （需解决的问题：理清各算法的原理，以及因此导致的适用范围）
· （状态：像不懂数学公式的意义，只会套用，不会变通）
· （问题列举：

判断环权值
字典序
求最长路径

---

算法：

Dijkstra 算法

解决对象 ：单源最短路径（边不能为负）
原理 ：每次松弛后，最近点的当前距离是其最短距离。
方法 ：

容器 ：

邻接矩阵图 graph[ ][ ] //记录各点间距（无距离为INF，自己到自己为0）
数组 marked[ ] //记录是否已得到最短路
数组 lenth[ ] //记录已得到的距离

过程：

1. 设初始点为 v
2. 通过 v 点更新 lenth[] 数据

   a. marked[v] = 1
   b. 选取 v 使 marked[v] == 0 且 lenth[v] 最小

3. 重复2直到 marked[] 中所有都为1

---

Floyd 算法

解决对象 ：图中每两个点的最短距离（边不为负）
原理 ：向路径中依次加入点，加入的点的距离已是当前最短。
              【子图dp思想】
问题 ：[floyd一定是对的吗？]([floyd算法:我们真的明白floyd吗? - CSDN博客]https://blog.csdn.net/ljhandlwt/article/details/52096932)
方法 ：

for(k=0;k<n;k++) {  
　　for(i=0;i<n;i++) {  
　　　　for(j=0;j<n;j++) {  
　　　　　　if(graph[I][j] > graph[I][k] + graph[k][j]) {  
　　　　　　　　graph[i][j] > graph[i][k] + graph[k][j])   
　　　　　　}  
　　　　}  
　　}  
} 

---

Bellman-Ford 算法

解决对象 ：单源最短路径/判断负权回路（复杂度较高）
原理 ：遍历每条边，每次遍历得到一个节点的最短距离（类似Dijkstra）。
               【简单遍历】
方法 ：

容器 ：

邻接矩阵图 graph[ ][ ] //记录各点间距
数组 lenth[ ] //储存最短距离

过程：

1. 设初始点为 v
2. 循环n-1次：

   a. 对每条边 edge(v,u), 如果 lenth[v]+edge(v,u) < lenth[u], 更新lenth[u]

3. （若需判断负环）再循环n-1次，若有边能被更新则说明有负环。

---

SPFA 算法

解决对象 ：单源最短路径（边可为负）（会因特殊数据导致复杂度很高）
原理 ：类似堆调整，对每个被更新过的节点进行更新。【相当于剪枝的遍历】
               【bellman的优化】
方法 ：

容器 ：

邻接矩阵图 graph[ ][ ] //记录各点间距
队列 queue //储存处理点v
数组 lenth[ ] //储存最短距离

过程：

1. 将起点入队
2. 出队v

   a.更新v周围点
   b.如果被更新，入队

3. 重复2直到队空

---

A* 算法

解决对象 ：在地图上找点对点最短路。
原理 ：类似Dijkstra算法，每次更新权值，并找当前点可达的权值最小点。
方法 ：

容器 ：

权值 F = G+H //G为从起点到当前点移动的距离，H为到终点的估计移动距离
数组 open[ ] //用于记录点是否可达
数组 close[ ] //用于记录点是否不可达（已走过或是墙）

过程：

1. 设起点为v
2. 遍历v周围可达点u，并做：

   a. u在close[ ]中，则跳过.
   b. u不在open[ ]中， 则加入open[]并计算权值F.
   c. u在open[ ]中，计算F并与原本权值比较，取较小.

3. 重复2，直到到达终点.

---

补充

关于路径：

一个巧妙的方法：
（在 HDU 1385 中实现过）
int path[ ][ ] //path[i][j]记录从i到j的第二个节点

---

回顾反思

学习过程回顾：

本次学习过程中经历了三个阶段：摸索算法->尝试运用->回顾剖析
       在第一个阶段中只是简单地罗列算法，像是本篇blog中每个算法的「方法」模块，知道过程，但只能死记硬背生搬硬套。
       在第二个阶段中，运用算法解题的过程中遭到了很多打击：选错算法、一直WA之类的。与此同时也在不断吸收各个题解的精华，对算法有进一步的了解。
       第三个过程则是在第二个过程中顿悟达到的。连续的挫败引发了总结的欲望，从题解中吸收的知识为成功总结打下基石。

反思：

  1.第一个阶段花费时间过多，状态较差，不清楚所作所为的目标。但时间花费还是必要的，「迷茫」也是入门阶段无法避免的挑战，下次还要更加打起精神来。
  2.达成主线任务(学习算法)的过程中还会遇到支线任务(markdown知识掌握)，做支线任务之余不能忘了把主要精力放在主线任务上。支线任务可以用于放松心情。（成就感十足）
  3.游戏什么的应该当作阶段性奖励，能很好地达到放松的目的，也能更好地推进任务完成。
  4.写博客实在是太爽了！（终于找到督促自己实时反思的途径了）

未解决问题（挖坑）：

1.markdown语法在hexo框架下显示错误

猜测：

是从 bear 复制到 Macdown 时发生错误*

解决：

去掉html下划线代码后，格式显示成功。也许是不兼容的原因。

2.blog图片的相对路径引用
（存放在文件夹的什么位置问题）

---

题目目录：
HDU 1217: Arbitrage
HDU 1224: Free DIY Tour
HDU 1385: Minimum Transport Cost
HDU 1869: 六度分离
HDU 1874: 畅通工程续
HDU 2066: 一个人的旅行
HDU 2112: HDU Today
HDU 2544: 最短路
HDU 2680: Choose the best route
HDU 2722: Here We Go(relians) Again
HDU 2923: Einbahnstrasse
HDU 3339: In Action
HDU 3790: 最短路径问题