首页 > 代码库 > Dijkstra算法
Dijkstra算法
Dijkstra算法和BellmanFord算法是两大经典的单源最短路径算法. Bellman支持负权重的边, 不支持负环. Dijkstra算法的效率更高, 不支持负边, 用处更广泛.
Dijkstra的基本过程如下:
- 初始化每一个节点: 对于源节点, 我们把距离(distance)字段设为0. 其他节点的distance字段设为正无穷
- 用一个最小优先队列存储所有节点. 所谓最小, 就是节点的distance最小
- 从队列里弹出一个节点, 该节点必然满足:从源节点到该节点的最短路径已经找到. 考虑该节点的邻接节点, 并计算所有邻接节点的distance字段, 即为可能的最短路径. 比较刚刚计算好的路径长度和邻接节点原来的distance值, 取最小的一方. (贪心策略: greedy strategy)
- 重复执行3. 当队列为空时, 从源节点到所有其他节点的最短带权路径已经计算好了, 算法返回
struct Vertice_comparator{ bool operator()(Vertice const * a, Vertice const * b) { return !!(a->distance > b->distance); }};typedef vector<Vertice*> Queue;void Graph::dijkstra(int source_id){ Vertice_comparator cmp = Vertice_comparator(); if ((*this)[source_id] == NULL) { printf_s("找不到源节点%d\n", source_id); return; }#pragma region 初始化 Queue q = Queue(); for (Node v : allVertices) { v.second->distance = v.first == source_id ? 0 : numeric_limits<int>::max(); q.push_back(v.second); }#pragma endregion 初始化 while (!q.empty()) { // 因为你要在队列外部改变Vertice*所指的内容 // 而priority_queue又没开放重新建堆的接口 // 所以用<algorithm>头文件里的make_heap建堆 make_heap(q.begin(), q.end(), cmp); Vertice* u = q.front(); cout << "当前结点 " <<u->id << endl; q.erase(q.begin()); // pop() for (Edge adj : u->adjacentVertices) { #pragma region 贪心 if ((adj.target->distance) > (u->distance+adj.weight)) { adj.target->distance = u->distance + adj.weight; } #pragma endregion 贪心 } }}
Dijkstra算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。