什么是最短路径问题
如果从图中某一顶点（称为源点）到达另一顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。
单源最短路径问题是指对于给定的图$g=(v, e)$，求源点$v_0$到其它顶点$v_t$的最短路径。
dijkstra算法
dijkstra算法用于计算一个节点到其他节点的最短路径。dijkstra是一种按路径长度递增的顺序逐步产生最短路径的方法，是一种贪婪算法。
dijkstra算法的核心思想是首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从源点$v_0$到其它各顶点的最短路径全部求出为止。
具体来说：图中所有顶点分成两组，第一组是已确定最短路径的顶点，初始只包含一个源点，记为集合$s$；第二组是尚未确定最短路径的顶点，记为集合$u$。
按最短路径长度递增的顺序逐个把$u$中的顶点加到$s$中去，同时动态更新$u$集合中源点到各个顶点的最短距离，直至所有顶点都包括到$s$中。
实现思路
初始时，$s$集合只包含起点$v_0$；$u$集合包含除$v_0$外的其他顶点$v_t$，且$u$中顶点的距离为起点$v_0$到该顶点的距离。（$u$中顶点$v_t$的距离为$(v_0, v_t)$的长度，如果$v_0$和$v_t$不相邻，则$v_t$的最短距离为$\infty$）
从$u$中选出距离最短的顶点$v_{t’}$，并将顶点$v_{t’}$加入到$s$中；同时，从$u$中移除顶点$v_{t’}$。
更新$u$中各个顶点$v_t$到起点$v_0$的距离以及最短路径中当前顶点的前驱顶点。之所以更新$u$中顶点的距离以及前驱顶点是由于上一步中确定了$v_{t’}$是求出最短路径的顶点，从而可以利用$v_{t’}$来更新$u$中其它顶点$v_t$的距离，因为存在$(v_0, v_t)$的距离可能大于$(v_0, v_{t’}) (v_{t’}, v_t)$距离的情况，从而也需要更新其前驱顶点
重复步骤(2)和(3)，直到遍历完所有顶点
案例分析
代码实现
使用了部分c 11特性，注释丰富，读起来应该不会太困难！
#include
#include
#include
#include
#include
using namespace std;
using matrix = vector>; // 连接矩阵（使用嵌套的vector表示）
using snodes = vector>; // 已计算出最短路径的顶点集合s（类似一个动态数组）
using unodes = list>; // 未进行遍历的顶点集合u（使用list主要是方便元素删除操作）
using enode = tuple; // 每个节点包含（顶点编号，当前顶点到起始点最短距离，最短路径中当前顶点的上一个顶点）信息
/***
* 从未遍历的u顶点集合中找到下一个离起始顶点距离最短的顶点
* @param unvisitednodes 未遍历的u顶点集合
* 每个元素是（顶点编号，当前顶点到起始点最短距离，最短路径中当前顶点的上一个顶点）的tuple
* @return 下一个离起始顶点距离最短的顶点
*/
enode searchnearest(const unodes &unvisitednodes) {
uint mindistance = uint_max;
enode nearest;
for (const auto &node: unvisitednodes) {
if (get<1>(node) <= mindistance) {
mindistance = get<1>(node);
nearest = node;
}
}
return nearest;
}
/***
* 迪克斯特拉算法的实现
* @param graph 连接矩阵（使用嵌套的vector表示）
* @param startnodeindex 起始点编码（从0开始）
* @return 返回一个vector，每个元素是到起始顶点的距离排列的包含（顶点编号，当前顶点到起始点最短距离，最短路径中当前顶点的上一个顶点）的tuple
*/
snodes dijkstra(const matrix &graph, uint startnodeindex) {
const uint numofnodes = graph.size(); // 图中顶点的个数
// s是已计算出最短路径的顶点的集合（顶点编号，当前顶点到起始点最短距离，最短路径中当前顶点的上一个顶点）
snodes visitednodes;
// u是未计算出最短路径的顶点的集合（其中的key为顶点编号，value为到起始顶点最短距离和最短路径中上一个节点编号组成的pair）
unodes unvisitednodes;
// 对s和u集合进行初始化，起始顶点的距离为0，其他顶点的距离为无穷大
// 最短路径中当前顶点的上一个顶点初始化为起始顶点，后面会逐步进行修正
for (auto i = 0; i < numofnodes; i) {
if (i == startnodeindex) visitednodes.emplace_back(i, 0, startnodeindex);
else unvisitednodes.emplace_back(i, graph[startnodeindex][i], startnodeindex);
}
while (!unvisitednodes.empty()) {
// 从u中找到距离起始顶点距离最短的顶点，加入s，同时从u中删除
auto nextnode = searchnearest(unvisitednodes);
unvisitednodes.erase(find(unvisitednodes.begin(), unvisitednodes.end(), nextnode));
visitednodes.emplace_back(nextnode);
// 更新u集合中各个顶点的最短距离以及最短路径中的上一个顶点
for (auto &node: unvisitednodes) {
// 更新的判断依据就是起始顶点到当前顶点（nextnode）距离加上当前顶点到u集合中顶点的距离小于原来起始顶点到u集合中顶点的距离
// 更新最短距离的时候同时需要更新最短路径中的上一个顶点为nextnode
if (graph[get<0>(nextnode)][get<0>(node)] != uint_max &&
graph[get<0>(nextnode)][get<0>(node)] get<1>(nextnode) < get<1>(node)) {
get<1>(node) = graph[get<0>(nextnode)][get<0>(node)] get<1>(nextnode);
get<2>(node) = get<0>(nextnode);
}
}
}
return visitednodes;
}
/***
* 对使用迪克斯特拉算法求解的最短路径进行打印输出
* @param paths vector表示的最短路径集合
* 每个元素是到起始顶点的距离排列的包含（顶点编号，当前顶点到起始点最短距离，最短路径中当前顶点的上一个顶点）的tuple
*/
void print(const snodes &paths) {
stack tracks; //从尾部出发，使用stack将每个顶点的最短路径中的前一个顶点入栈，然后出栈的顺序就是最短路径顺序
// 第一个元素是起始点，从第二个元素进行打印输出
for (auto it = paths.begin(); it != paths.end(); it) {
// 打印头部信息
printf("%c -> %c:\t length: %d\t paths: %c",
char(get<0>(paths[0]) 65),
char(get<0>(*it) 65),
get<1>(*it),
char(get<0>(paths[0]) 65));
auto pointer = *it;
// 如果当前指针pointer指向的节点有中途节点（判断的条件是最短路径中的前一个节点不是起始点）
while (get<2>(pointer) != get<0>(paths[0])) {
tracks.push(get<0>(pointer));
// lambda表达式，使用find_if函数把当前顶点的前一个顶点从paths中找出来继续进行循环直到前一个节点就是起始点
auto condition = [pointer](tuple x) { return get<0>(x) == get<2>(pointer); };
pointer = *find_if(paths.begin(), paths.end(), condition);
}
tracks.push(get<0>(pointer));
// 以出栈的顺序进行打印输出
while (!tracks.empty()) {
printf(" -> %c", char(tracks.top() 65));
tracks.pop();
}
printf("\n");
}
}
int main() {
matrix graph = {
{0, 12, uint_max, uint_max, uint_max, 16, 14},
{12, 0, 10, uint_max, uint_max, 7, uint_max},
{uint_max, 10, 0, 3, 5, 6, uint_max},
{uint_max, uint_max, 3, 0, 4, uint_max, uint_max},
{uint_max, uint_max, 5, 4, 0, 2, 8},
{16, 7, 6, uint_max, 2, 9, 9},
{14, uint_max, uint_max, uint_max, 8, 9, 0}
}; // 图对应的连接矩阵
auto results = dijkstra(graph, uint('d' - 65)); // 选取顶点c（大写字母a的ascii编码是65）
print(results); // 打印输出结果
return 0;
}
运行结果：
d -> c: length: 3 paths: d -> c
d -> e: length: 4 paths: d -> e
d -> f: length: 6 paths: d -> e -> f
d -> g: length: 12 paths: d -> e -> g
d -> b: length: 13 paths: d -> c -> b
d -> a: length: 22 paths: d -> e -> f -> a