算法可视化
数据结构
最短路径:Dijkstra 算法
贪心求单源最短路:每次选距离最短的未确定点,用它去更新邻居(松弛)。边上的数字是权重。
main.cpp第 2 行
1// Dijkstra: 从 0 到所有点的最短距离
2dist[0] = 0; // 其余为 ∞
3while (还有未确定的点) {
4 u = 未确定中 dist 最小的点;
5 visited[u] = true; // 确定 u
6 for (v : adj[u])
7 dist[v] = min(dist[v], dist[u] + w(u,v)); // 松弛
8}
变量表0 个变量
还没有变量,执行到声明语句后出现
图(节点 + 边)
1/19
初始化:dist[0] = 0,其余节点距离为 ∞
1 / 19