单元最短路径dijkstra代码
时间: 2023-12-20 14:28:20 浏览: 29
Dijkstra算法是一种用于计算图中单源最短路径的贪心算法。它的基本思想是从起点开始,逐步扩展到其他节点,直到到达终点。在扩展的过程中,每次选择当前距离起点最近的一个节点,并更新与该节点相邻的节点的距离。下面是Dijkstra算法的伪代码:
```
1. 初始化:将起点s的距离dist[s]设为0,其余节点的距离dist[i]设为无穷大。
2. 将所有节点加入集合S中。
3. while S不为空:
a. 从集合S中选取一个距离起点最近的节点u。
b. 对于u的每个邻居节点v,如果dist[u]+w(u,v)<dist[v],则更新dist[v]=dist[u]+w(u,v)。
c. 将节点u从集合S中删除。
4. 返回dist数组。
其中,w(u,v)表示节点u到节点v之间的边权值。
下面是Dijkstra算法的C++代码实现:
```
const int INF = 0x3f3f3f3f; // 定义无穷大
int dist[N]; // 存储起点到各个节点的最短距离
bool vis[N]; // 标记节点是否已经被访问过
vector<pair<int, int>> adj[N]; // 存储图的邻接表
void dijkstra(int s) {
memset(dist, INF, sizeof(dist)); // 初始化距离为无穷大
memset(vis, false, sizeof(vis)); // 初始化所有节点未被访问过
dist[s] = 0; // 起点到自身的距离为0
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 小根堆
pq.push(make_pair(0, s)); // 将起点加入小根堆
while (!pq.empty()) {
int u = pq.top().second; // 取出距离起点最近的节点u
pq.pop();
if (vis[u]) continue; // 如果节点u已经被访问过,则跳过
vis[u] = true; // 标记节点u已经被访问过
for (auto e : adj[u]) { // 遍历节点u的所有邻居节点
int v = e.first; // 邻居节点v
int w = e.second; // 边权值w(u,v)
if (dist[u] + w < dist[v]) { // 如果从起点到节点u再到节点v的距离比起点直接到节点v的距离更短,则更新dist[v]
dist[v] = dist[u] + w;
pq.push(make_pair(dist[v], v)); // 将节点v加入小根堆
}
}
}
}
```
--相关问题--: