dijkstra单源最短路

dijkstra算法用于计算图中某一点到其他各点的最短路径，要求各路径的权值不能为负。

算法流程

设图中共有n个点，记源点为s，d[i]表示从s到i的最短路径长度。

• 初始化
  • 顶点集合 V = {}
  • 距离数组 d[s] = 0，其他d[i] = INF
• 循环n次
  • 找到节点i不属于V，且d[i]值最小
  • V = V + i
  • 对所有满足j属于V的边(i,j)，更新d[j] = min(d[j], d[i] + w(i,j))

例题：单源最短路

struct HeapNode {
    int idx, dst;
    bool operator<(const HeapNode &o) const {
        return dst > o.dst;
    }
};
int n, m, S, T, d[1005], vis[1005];
vector<pair<int,int> > g[1005];
priority_queue<HeapNode> q;
int main() {
    int a, b, c;
    scanf("%d%d%d%d", &n, &m, &S, &T);
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        g[a].push_back(make_pair(b, c));
        g[b].push_back(make_pair(a, c));
    }
    for (int i = 1; i <= n; i++) d[i] = INT_MAX;
    q.push((HeapNode){S, 0});
    while (!q.empty()) {
        HeapNode t = q.top(); q.pop();
        int x = t.idx;
        if (vis[x]) continue;
        vis[x] = 1; d[x] = t.dst;
        for (auto i : g[x]) if (!vis[i.first])
            q.push((HeapNode){i.first, d[x] + i.second});
    }
    printf("%d\n", d[T]);
    return 0;
}

如果除了最短路径外，还需要求出最短路线，可以设置fa数组，将节点加入优先队列时把父节点标号也一并写入，在更新d数组时记录节点的父节点，最后逆序输出即可。