【1】【2】分别给出了有向非负权网的最短路径的算法，前者是图中任意两点的. 后者是单源的. 但是不论是floyd还是dijkstra，都要求不含负权边. 那么对于含有负权边有什么办法求出最短路径呢? bellman-ford就此诞生. 该算法不仅可以求出可能含有负权边的有向图单源最短路径，或者如果存在负权环的导致不存在最短路径则能检测出来.

2019-05-27

floyd算法

缘起

floyd算法是求有向非负权网任意两点之间的最短路径.

2019-05-27

dijkstra算法

缘起

dijkstra算法是非负权有向网到单源的最短路径的算法.

dijkstra算法的证明:

如果在某一轮中一个顶点i是d[i] 最短的那个（从而i需要加入U，而引入i的掮客是j）. 那么d[i]就是单源0到i的最短路径了. 反证法. 如果存在别的路径0–>x–>i更小的话, 则考虑x有没有加入U呢? 如果已经在U中了, 那么为什么i没有在x选择的时候就加入呢? 如果尚没有在U中, 0–>x比d[i]还大, 又怎么可能0–>x–>i短于d[i]呢? （除非x–>i是负权边，所以dijkstra不允许有负权边）

2019-05-27

希尔排序

缘起

本文介绍一下一种直接插入排序的推广——希尔（Shell）排序. 该算法基于以下事实：如果一个序列基本有序，那么用直接插入排序是非常快的，因为while的第一步就会终止. 希尔排序就是选取一定的步长，将序列整的基本有序（所谓基本有序是指大的数基本在后面，小的数基本在前面，而不是局部有序）
ps：因为涉及不相邻元素之间的调换，所以希尔排序不是稳定排序，但是显然是就地算法.

2019-05-26

A-star 寻路算法

缘起

我们学过图的dfs和bfs，并且知道了他们都可以用于求解最短路径. 而且在【1】中指出了

其实各种搜索框架的本质不同就是如何对待发现的顶点. 深搜是最后处理最先发现的顶点（对应数据结构就是栈），而宽搜不同, 宽搜是最先处理最先发现的顶点（对应的数据结构就是队列）

所以其实我们可以将搜索框架进行推广——给所有顶点赋予不同的优先级，而且随着算法的推进不断调整；而每一步迭代所选取的顶点，都是当时的优先级最高者。按照这种理解，包括BFS和DFS在内的几乎所有图搜索，都可纳入统一的框架。所以优先队列这种数据结构，也就是堆这种数据结构在一般搜索框架中将扮演重要角色. 堆的相关知识参见【2】. 而本文将介绍一种重要的游戏AI寻路基本算法——A*算法

2019-05-26