#include "Dijistra.h"

unordered_map<Node*, int> Dijistra::dijistra(Graph graph, Node* node) {
	unordered_map<Node*, int> dist;
	unordered_set<Node*> markednode;
	dist[node] = 0;
	markednode.insert(node);
	//有哪些点可以直接到达node节点，更新dist
	for (auto edge:node->edges) {
		Node* to = edge->to;
		dist[to] = edge->weight;
	}
	//循环n-1次
	int n = graph.nodes.size();
	n--;
	while (n) {
		int mindist = INT_MAX;
		Node* minnode;
		for (auto nodepair : dist) {
			//如果这个节点没有被标记过
			if (markednode.find(nodepair.first)==markednode.end()&&nodepair.second<mindist) {
				mindist = nodepair.second;
				minnode = nodepair.first;
			}
		}
		//找到最小距离的节点标记一下
		markednode.insert(minnode);
		//更新dist，那些节点能通过minnode到达node
		for (auto edge : minnode->edges) {
			Node* tmp = edge->to;
			if (markednode.find(tmp)==markednode.end()) {
				int distance = mindist + edge->weight;
				if (dist.find(tmp) == dist.end()) {
					dist[tmp] = distance;
				}
				else {
					if (dist[tmp] > distance) {
						dist[tmp] = distance;
					}
				}
			}
		}



		n--;
	}
	return dist;
}