迪杰斯特拉算法

介绍

Dijkstra 算法由荷兰计算机科学家 E. W. Dijkstra 于 1956 年发现，1959 年公开发表。是一种求解非负权图上单源最短路径的算法。

图示

实现 Dijkstra 算法需要维护两个集合和一个哈希表，第一个集合存储已经访问的节点，第二个集合存储未访问的节点，哈希表用于存储各个节点到起点的距离权重。
在进行一轮算法时，查找第一个集合内元素的相邻元素，将距离原点距离最短的元素加入第一个集合，与此同时在第二个集合内删去该元素，更新距离哈希表。

例如，设置起点为0，第一个集合为：{0}，第二个集合为：{1,2,3,4,5,6}，哈希表初始化为：

{$0:0,1:\infty,2:\infty,3:\infty,4:\infty,5:\infty,6:\infty$}

1. 从0节点开始，可以到达1、2两个节点。

更新集合1：{0,2}
只选择哈希表内距离最近的节点，抛弃1节点

更新集合2：{1,3,4,5,6}

更新哈希表：
经过0号节点到达1号节点的距离是5，到达2号节点的距离是2，有：

{$0:0,1:5,2:2,3:\infty,4:\infty,5:\infty,6:\infty$}

2. 从2节点开始，可以到达3、5两个节点；从0号节点开始，可以到达1节点。

更新集合1：{0,1,2}
只选择哈希表内距离最近的节点，抛弃3、5节点

更新集合2：{3,4,5,6}

更新哈希表：
经过2号节点到达3号节点的距离是2+6，到达5号节点的距离是2+8；

哈希表内节点距离取最小，有：
{$0:0,1:5,2:2,3:8,4:\infty,5:10,6:\infty$}

3. 从2节点开始，可以到达3、5两个节点；从1号节点开始，可以到达3、4节点。

更新集合1：{0,1,2,3}
只选择哈希表内距离最近的节点，抛弃4、5节点

更新集合2：{4,5,6}

更新哈希表：
经过1号节点到达3号节点的距离是5+1，到达4号节点的距离是5+6；
哈希表内节点距离取最小，有：
{$0:0,1:5,2:2,3:6,4:11,5:10,6:\infty$}

依次类推，当最后集合2为空时，算法结束，哈希表内为最短路径。

详细演示

---

算法示例

对邻接矩阵进行迪杰斯特拉算法

   class Dijkstra{
	public:
		// static graph, nodes num, start node 
		Dijkstra(std::vector<std::vector<int>>g, int n, int k):g(g),n(n),k(k){}
	private:
		std::vector<std::vector<int>>g;
		int n;
		int k;	
	public:
		std::vector<int> GetDistance(){
		    std::vector<int> dist(n, INT_MAX/2);
		    dist[k - 1] = 0;
		    std::vector<bool> used(n);
		    for (int i = 0; i < n; ++i) {
		        int x = -1;
		        for (int y = 0; y < n; ++y) {
		            if (!used[y] && (x == -1 || dist[y] < dist[x])) {
		                x = y;
		            }
		        }
		        used[x] = true;
		        for (int y = 0; y < n; ++y) {
		            dist[y] = std::min(dist[y], dist[x] + g[x][y]);
		        }
		    }
		    return dist;
		}
};

---

算法分析

1. 时间复杂度 $O(n^2)$
2. 空间复杂度 $O(n)$

---

例题

1. leetcode 743.网络延迟时间