Dijkstra求最短路径

利用了广度优先搜索，使用贪心思想，不断扫描各点距离源点的距离，然后将最短距离保存，直到所有点扫描完毕。

详见青大王卓课程：https://www.bilibili.com/video/BV1nJ411V7bd?p=132，该p一步一步的推导迪杰斯特拉算法如何实现。

从源点v0出发，求得到其余所有点的距离，打成第一张表，然后以此表为依据，寻找距离v0最近的点，将该点加入到v0的点集S中；

进行第二次打表，本次打表不是从v0出发，而是从点集S出发，求得S到各点的最短距离，将距离最短的点更新加入S，然后不断重复，直到目标点被添加入点集S时，结束，此时找到最短路径。

三步走，到最优的dj算法。dj算法可以说是贪心的一种，bfs思想的延展。

1.暴力寻找（不用bfs思想）（不是dj）

	while (!q.empty()) {
		int t = q.front(); q.pop();
		for (int i = h[t]; i != -1; i = ne[i]) {
			int b = e[i];
			if (dist[t] + v[i] < dist[b]) {
				dist[b] = dist[t] + v[i];
				q.push(b);
			}
		}
	}
// 这是很暴力的写法，把原点放进去后，然后bfs原点，但是每次遇到更新，都会把更新的点重新走一遍
// 这样写其实是有悖与bfs算法的

2.dj思想解决sssp：
(紫书)

设d[0]=0;d[i]=INF;
循环n次{
    在所有未标记结点中，选出d值最小的结点x // 这个是dj中用到bfs思想
    给结点x标记
    对于从x出发的所有边(x,y)，更新d[y] = min(d[y], d[x]+w(x,y))
}

朴素实现：

int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点   （这个地方可以使用堆进行优化）
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

作者：yxc
链接：https://www.acwing.com/blog/content/405/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

堆优化版：

	while (!q.empty()) {
		auto tP = q.top();
		int t = tP.second; q.pop();// 从这里取出来的一定是最小的
		if(st[t])continue; 
		st[t] = 1;	
		for (int i = h[t]; i != -1; i = ne[i]) { // 这个地方不可避免的得放入进堆
			int b = e[i];
			if (dist[t] + v[i] < dist[b]) {
				dist[b] = dist[t] + v[i];
				q.push({dist[b], b});
			}
		}
	}