7-1 Dijkstra算法（模板

Dijkstra算法是一种用于解决带权图的单源最短路径问题的贪心算法。它维护一个距离起点的最短路径已知的顶点集合，通过不断地扩展这个集合，最终得到从起点到所有顶点的最短路径。

Dijkstra算法的基本思想是，维护一个集合S，表示已经求出最短路径的顶点集合。一开始，S只包含起点。然后，每次从集合V-S中选取一个距离起点最近的顶点u，将其加入集合S中，并更新与u相邻的所有顶点的最短路径。

具体实现上，我们可以使用一个数组dis[]来存储每个顶点到起点的最短路径长度，数组vis[]表示该顶点是否已经被加入到集合S中。每次选取距离起点最近的顶点u后，我们遍历u的所有邻居v，并更新dis[v]的值，如果dis[v]发生了改变，我们就将v加入到一个优先队列中，等待下一次选择。

以下是Dijkstra算法的伪代码实现：

int n; // 顶点数
int dis[N]; // 存储起点到每个顶点的最短距离
bool vis[N]; // 标记每个顶点是否已经加入集合S中
vector<pair<int, int>> adj[N]; // 存储每个顶点的邻居

void dijkstra(int s) { // s为起点编号
    memset(dis, 0x3f, sizeof dis); // 将dis数组初始化为无穷大
    dis[s] = 0; // 起点到自身的距离为0
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push({0, s}); // 将起点加入队列中
    while (!q.empty()) {
        auto t = q.top(); q.pop();
        int u = t.second;
        if (vis[u]) continue; // 如果该点已经在集合S中，直接跳过
        vis[u] = true; // 将u加入集合S中
        for (auto [v, w] : adj[u]) { // 遍历u的所有邻居
            if (dis[v] > dis[u] + w) { // 如果从u到v的距离更短
                dis[v] = dis[u] + w; // 更新dis数组
                q.push({dis[v], v}); // 将v加入队列中
            }
        }
    }
}

其中，priority_queue是一个优先队列，用于存储待选顶点。我们使用了STL中的pair来表示顶点与其到起点的距离。优先队列默认按照pair的第一个元素排序，因此我们需要自定义一个比较函数，将pair按照第二个元素（距离）排序。

Dijkstra算法的时间复杂度为O(ElogV)，其中E为边数，V为顶点数。在实际应用中，Dijkstra算法的效率很高，能够处理大规模的图。