迪杰斯特拉 Dijkstra | 单源最短路径

适用问题

使用于求单个源的最短路径（单源到单目的或多目的均可），要求边的权重非负。

算法

pseudo code from wiki

时间复杂度：
访问条边，优先队列中元素个数为，所以复杂度为

示例代码

见github

参考

• wiki: Dijkstra's_algorithm
• geeksforgeeks: Dijkstra’s Shortest Path Algorithm using priority_queue of STL