荷兰计算机科学家 Edsger Dijkstra在1959年提出了一种可以应用于加权图的算法。该加权图可以是有向的，也可以是无向的，条件是加权图需要在每条边上包含一个非负值。这个算法以他的名字作为命名——“Dijkstra算法”。
什么是Dijkstra算法？
简单解释，用于在加权图中找到从起始节点到目标节点的最短距离或路径的算法称为Dijkstra算法。该算法生成从起始节点（源节点）到图中所有其他节点的最短路径树。
Dijkstra算法利用边的权重来寻找使源节点和所有其他节点之间的总距离（权重）最小的路径。该算法也称为单源最短路径算法。
Dijkstra算法是迭代算法过程，为我们提供从一个特定起始节点到图的所有其他节点的最短路径。它与最小生成树不同，因为两个顶点之间的最短距离可能不会涉及到图的所有顶点。
需要注意的是，Dijkstra算法仅适用于所有权重为正的情况，因为在执行过程中，是将边的权重相加以找到最短路径。
因此，如果在图的边缘引入任何权重为负，则该算法将永远无法正常工作。但是，在这种情况下可以使用一些算法，例如Bellman-Ford算法。
众所周知，广度优先搜索(BFS)可用于计算未加权图的最短路径，或者用于在所有边上具有相同成本的加权图。
但是，如果加权图在其所有边的成本不相等，则BFS会推断出统一成本搜索。怎么办？
统一成本搜索不是按照从根开始的深度顺序扩展节点，而是按照从根开始的成本顺序来开发节点。该算法的一个变体被接受为Dijkstra 算法。
通常，Dijkstra算法的工作原理是松弛原理，其中精确距离的近似值被更合适的值稳定地置换，直到达到最短距离。
此外，到每个节点的估计距离始终是真实距离的高值，并且通常用最近确定的路径的距离代替其先前值中的最小值。
它使用优先级队列贪婪地选择尚未访问的最近节点，并在其所有边上执行松弛过程。
Dijkstra算法算法示例
想要计算源 A 和目标 D 之间的最短距离，同时计算一个子路径，该子路径也是其源和目标之间的最短路径。
任何子路径，假设顶点 A 和 D 之间的最短路径的子路径 B 到 D 也是顶点 B 和 D 之间的最短路径，即每个子路径都是最短路径。
在这里，Dijkstra 的算法在相反的方向使用此属性，这意味着，在确定距离时，我们高估了每个顶点到起始顶点的距离，然后检查每个节点及其邻居以检测到这些邻居的最短子路径。
这样，算法通过搜索下一个合理的解决方案来部署贪婪方法，并期望最终结果将是整个问题的适当解决方案。
Dijkstra算法基本特征
基本上，Dijkstra算法从要选择的节点开始，即源节点，它检查整个图以确定该节点与图中所有其他节点之间的最短路径。
该算法维护当前识别的从每个节点到源代码的最短距离的轨迹，如果它识别出另一条最短路径，则更新这些值。
一旦算法确定了源代码中到另一个节点的最短路径，该节点就会被标记为“已访问”并且可以添加到路径中。
这个过程一直持续到图形中的所有节点都已添加到路径中，这样就创建了一条路径，该路径将源节点连接到遵循合理最短路径的所有其他节点以到达每个节点。
Dijkstra算法的优缺点
Dijkstra算法的优点：
1、线性的几乎没有复杂性。
2、可用于计算单个节点到所有其他节点和单个源节点到单个目标节点之间的最短路径，一旦目标节点达到最短距离，就停止算法。
Dijkstra算法的缺点：
1、在处理时会消耗大量时间
2、仅适用于有向加权图，无法处理边为负值
