使用图的Dijkstra算法,求出最短路径长度成功,怎么样才能输出,最短路径经过的节点
//unordered_map<int,vector<int>> L;
Node* getMinDistanceAndUnselectNode(unordered_map<Node*,int> dijkstraMap,unordered_set<Node*> selectNode){
Node* minNode = NULL;
int minDistance = 100000;
for(auto entry:dijkstraMap){
Node* node = entry.first;
int key = entry.second;
if(!selectNode.count(node) && key < minDistance){
minNode = node;
minDistance = key;
}
}
return minNode;
}
//Dijkstra算法
unordered_map<Node*,int> Dijkstra(Node* head){
//从head出发到所有点的最小距离
//key:从head出发到key
//value:从head出发到达key的最小距离
//如果表中,没有T的记录,含义是从head出发到T这个点的距离为正无穷
unordered_map<Node*,int> dijkstraMap;
//L[head->value] = {head->value};
dijkstraMap[head] = 0;
//已经求距离的节点,存在selectNode中,以后再也不碰
unordered_set<Node*> selectNode;
//从dijkstraMap里面找没有被锁住并且离head最近的节点,存在selectNode
Node* minNode = getMinDistanceAndUnselectNode(dijkstraMap,selectNode);
while (minNode!=NULL){
cout<<"minNode:"<<minNode->value<<endl;
//L[minNode->value].push_back(toNode->value);
//先拿到head到minNode的距离
int distance = dijkstraMap[minNode];
//遍历minNode的边集
for(auto edge : minNode->edges){
//拿到minNode的边的to点
Node* toNode = edge->to;
//如果to点没有锁住
if(!dijkstraMap.count(toNode)){
//在dijkstraMap里更新to点的信息,距离为head到minNode的距离加上边的weight权值
dijkstraMap[toNode] = distance + edge->weight;
cout<<"toNode:"<<toNode->value<<endl;
//L[minNode->value].push_back(toNode->value);
}
//如果toNode是已经锁住的点,比较原来的dijkstraMap和加上权值后的distance,选更小的那个
dijkstraMap[edge->to] = dijkstraMap[toNode] < distance + edge->weight ? dijkstraMap[toNode] : distance + edge->weight;
}
selectNode.insert(minNode);
minNode = getMinDistanceAndUnselectNode(dijkstraMap,selectNode);
}
return dijkstraMap;
}
输出最短路径经过的节点