思维导图

Polar(int dist, int id) : dist(dist), id(id){} };

然后确定

struct cmp{ bool operator ()(Polar a, Polar b){ // 重载()运算符，使其成为一个仿函数

return a.dist > b.dist;// 这里是大于，使得距离短的先出队 }

};

priority_queue<Polar, vector<Polar>, cmp> Q;//小顶堆 int vis[n] //建立是否访问过的节点判断数组

算法实现：

void Dij(int s)

{ dist[s] = 0;

Q.push(Polar(0, s));

while (!Q.empty())

{ int p = Q.top().id;

Q.pop();

if (vis[p])

continue;

vis[p] = 1;

for (int e = head[p]; e != 0; e = edges[e].next)

{ int to = edges[e].to;

dist[to] = min(dist[to], dist[p] + edges[e].w);

if (!vis[to])

Q.push(Polar(dist[to], to));

} }

}

怎样打印路径？

只需要建立一个pre数组，在更新dist时候更新pre即可。由于算法最后的结果是一棵树，因此数组中保存此编号节点的父节点即可。每条路有且仅有一个祖先节点，一步步溯源上去的路径是唯一的。

思维导图

算法总结

链表