目录
一、Dijkstra算法
二、核心思路
三、步骤
四、代码
一、Dijkstra算法
迪杰斯特拉(Dijkstra)算法是由荷兰计算机科学家狄克斯特拉于1959年提出的。是寻找从一个顶点到其余各顶点的最短路径算法，可用来解决最短路径问题。
二、核心思路
迪杰斯特拉算法采用贪心算法的策略，将所有顶点分为已标记点和未标记点两个集合，从起始点开始，不断在未标记点中寻找距离起始点路径最短的顶点，并将其标记，直到所有顶点都被标记为止。
所以我们需要准备一个起始点到其他点最短距离的一张表，和一个挑选节点的表,如下
//从headnode出发到所有点最小距离的表
//key: 从headnode出发到达key的点
//value: 从headnode出发到达key的最小距离
unordered_map
//先放入头节点，头节点到头节点的距离为0，其他为解锁的节点距离为正无穷
distanceMap.insert(make_pair(headnode, 0));
//有一个记录节点的表，使用完一个节点之后放入表中不再使用
set
需要注意的一点是该方法不能处理带有负权边的图，下面我们举出一个实例并通过迪杰斯特拉方法对其进行求解。
三、步骤
1、选一个minNode
2、考察minNode的所有边，判断边的toNode节点是否在set表中
3、如果不在表中，说明该点未被考察过，更新最小距离
4、在表中判断distanceMap中到该点的距离和现在走的这条路到该点的距离谁小，然后更新
5、重复1-4，直到所有的点被set表锁住结束整个流程
图解：
重复上述步骤最终可以得到A点到所有点的最短路径的一个表
四、代码
//Dijkstra的经典写法，有改写堆的优化
class Solution
{
public:
unordered_map
//从headnode出发到所有点最小距离的表
//key: 从headnode出发到达key的点
//value: 从headnode出发到达key的最小距离
unordered_map
//先放入头节点，头节点到头节点的距离为0，其他为解锁的节点距离为正无穷
distanceMap.insert(make_pair(headnode, 0));
//有一个记录节点的表，使用完一个节点之后放入表中不再使用
set
//拿距离headnode最近并且没有被锁住的点
Node* minNode = getMinNodeAndUnSelect(distanceMap, selectNodes);
//一直更新minNode，直到最后所有点都被锁住，minNode == nullptr，所以完成整个流程
while (minNode != nullptr) {
int distance = distanceMap[minNode];
for (auto edges : minNode->edges) {
Node* toNode = edges->to;
if (!selectNodes.count(toNode)) {
distanceMap.insert(make_pair(toNode, distance + edges->weight));
}
distanceMap.insert(make_pair(toNode, min(distanceMap[toNode], distance + edges->weight)));
}
selectNodes.insert(minNode);
minNode = getMinNodeAndUnSelect(distanceMap, selectNodes);
}
return distanceMap;
}
//返回距离headnode最近并且没有被锁过的点
Node* getMinNodeAndUnSelect(unordered_map
Node* minNode = nullptr;
int minDistance = INT_MAX;
for (auto pair : distance) {
Node* getNode = pair.first;
int getDistance = pair.second;
if (!touchNode.count(minNode) && getDistance < minDistance) {
minNode = getNode;
minDistance = getDistance;
}
}
return minNode;
}
};
发表评论