最短路径问题是图论研究中一个经典算法问题，旨在寻找图中两节点或单个节点到其他节点之间的最短路径。根据问题的不同，算法的具体形式包括：
常用的最短路径算法包括：Dijkstra算法，A 算法，Bellman-Ford算法，SPFA算法（Bellman-Ford算法的改进版本），Floyd-Warshall算法，Johnson算法以及Bi-direction BFS算法。本文将重点介绍Dijkstra算法的原理以及实现。
Dijkstra算法，翻译作戴克斯特拉算法或迪杰斯特拉算法，于1956年由荷兰计算机科学家艾兹赫尔.戴克斯特拉提出，用于解决赋权有向图的 单源最短路径问题 。所谓单源最短路径问题是指确定起点，寻找该节点到图中任意节点的最短路径，算法可用于寻找两个城市中的最短路径或是解决著名的旅行商问题。
问题描述 ：在无向图 中， 为图节点的集合， 为节点之间连线边的集合。假设每条边 的权重为 ，找到由顶点 到其余各个节点的最短路径（单源最短路径）。
为带权无向图，图中顶点 分为两组，第一组为已求出最短路径的顶点集合（用 表示）。初始时 只有源点，当求得一条最短路径时，便将新增顶点添加进 ，直到所有顶点加入 中，算法结束。第二组为未确定最短路径顶点集合（用 表示），随着 中顶点增加， 中顶点逐渐减少。
以下图为例，对Dijkstra算法的工作流程进行演示（以顶点 为起点）：
注：
01） 是已计算出最短路径的顶点集合；
02） 是未计算出最短路径的顶点集合；
03） 表示顶点 到顶点 的最短距离为3
第1步 ：选取顶点 添加进
第2步 ：选取顶点 添加进 ，更新 中顶点最短距离
第3步 ：选取顶点 添加进 ，更新 中顶点最短距离
第4步 ：选取顶点 添加进 ，更新 中顶点最短距离
第5步 ：选取顶点 添加进 ，更新 中顶点最短距离
第6步 ：选取顶点 添加进 ，更新 中顶点最短距离
第7步 ：选取顶点 添加进 ，更新 中顶点最短距离
示例：node编号1-7分别代表A,B,C,D,E,F,G
(s.paths <- shortest.paths(g, algorithm = "dijkstra"))输出结果：
(s.paths <- shortest.paths(g,4, algorithm = "dijkstra"))输出结果：
示例：
找到D（4）到G（7）的最短路径：
[1] 维基百科，最短路径问题： https://zh.wikipedia.org/wiki/%E6%9C%80%E7%9F%AD%E8%B7%AF%E9%97%AE%E9%A2%98 ；
[2]CSDN，Dijkstra算法原理： https://blog.csdn.net/yalishadaa/article/details/55827681
[3]RDocumentation: https://www.rdocumentation.org/packages/RNeo4j/versions/1.6.4/topics/dijkstra
[4]RDocumentation: https://www.rdocumentation.org/packages/igraph/versions/0.1.1/topics/shortest.paths
[5]Pypi: https://pypi.org/project/Dijkstar/
Dijkstra算法用于构建 单源点的最短路径树 (MST)——即树中某个点到任何其他点的距离都是最短的。例如，构建地图应用时查找自己的坐标离某个地标的最短距离。可以用于有向图，但是 不能存在负权值 (Bellman-Ford可以处理负权值)。
Prim算法用于构建 最小生成树 ——即树中所有边的权值之和最小。例如，构建电路板，使所有边的和花费最少。只能用于 无向图 。
//无向图G, 权值w, 起始点r
MST(G, w, r) {
for each u in G,V {
//此处做初始化操作，给每个节点u赋键值+∞，设置空为父节点
u.key = +∞
u.parent = NULL
}
//选初始点r，Q是无向图G中所有点V的权值优先队列，key可看作u到下一个节点v的距离
r.key = 0
Q = G,V
while(Q != ∅) ｛
//取出Q中权值最小值的点u
u = extractMin(Q)
//取点u连接的所有节点(即无向图G的邻接表中的第u个链表)
for each v ∈ G.Adj[u] {
if (v ∈ Q) and (w(u, v) <key) {
//若该节点仍在Q中且权值w(w,v)小于其原始权值，则进行松弛操作！
v.parent = u
v.key = w(u, v)
}
}
}
}
struct qnode 里面用的是 C++ 的语法，把结构体当做一个类来定义。语句解析：
1) qnode (int vv = 0, typec cc = 0) : v(vv), c(cc) {}
a）函数 qnode 是 struct qnode 的构造函数，
b）参数有两个：int w 和 typec c ，都有默认值 0 。默认值的作用是调用 qnode 这函数的时 候，如果不给参数传值，那么就是用默认值，如：
qnode(1,2)// 给第一个参数w 和第二个参数 cc 都制定值
qnode(3)// 等价于 qnode(3,0)第二个参数 cc 使用默认值 0
qnode()// 等价于 qnode(0,0)第一个参数w 和第二个参数 cc 都使用默认值 0
c）":" 后面的 v(w),c(cc) 是给结构体里面定义的两个变量 int vtypec c赋值，
相当于：v=w,c=cc如果不用这种形式，还可以改成：
qnode (int vv = 0, typec cc = 0) {v=w,c=cc}
2) bool operator <(const qnode&r) const { return c>r.c}
a) 这是重载运算符"<"，也就是“小于号”，让小于号两边的操作数可以是结构体 struct qnode。
比如:
struct qnode a,b
/*
只有重载运算符"<"，a<b 才能编译通过，否则编译无法通过，
因为C(C++)编译器默认是不知到如何比较两个 sturct qnode 类型的变量的。
*/
if(a<b){}
b) 上面例子中的 if(a<b) 具体是如何比较的呢？
我们假设：a.c = 1b.c = 2
那么通过函数体里面：
return c>r.c
我们知道两个 struct qnode 比较的时候，只和结构体里面的 typec c 变量有关，和其他变量无关。
因此 a<b 返回真。
![r语言mean(x[c1])什么意思](/aiimages/r%E8%AF%AD%E8%A8%80mean%28x%5Bc1%5D%29%E4%BB%80%E4%B9%88%E6%84%8F%E6%80%9D.png)
