图的迪杰斯特拉算法1（有向、无负权值的图）

way：找出从源点到其他所有的点的最短的那些路径们，(也叫单源最短路径法），从源点开始，好，先选源点（因为源点到自己的距离最小），然后从源点出发到其他新老节点的distance更新一下，好，再选一个从源点到未选择的点里面距离最小的点，更新新老节点的distance，选完之后将更新完的distanceMap返回。

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
 
class Node;
 
//边结构的描述
class Edge
{
public:
	//边的起始节点
	Node *from;
	//边的终点节点
	Node *to;
	//边的权重
	int weight;
public:
	Edge(Node *from, Node *to, int weight)
	{
		this->from = from;
		this->to = to;
		this->weight = weight;
	}

	定义比较函数，这样在优先队列中就可以进行比较了
	//bool operator<(const Edge& e)
	//{
	//	return this->weight < e.weight;
	//}
};
 
//点结构的描述
class Node
{
public:
	//编号值
	int value;
	//入度
	int in;
	//出度
	int out;
	//邻接的点
	vector<Node*> nexts;
	//邻接的边
	vector<Edge*> edges;
public:
	Node()
	{
	}
	Node(int value)
	{
		this->value = value;
		in = 0;
		out = 0;
	}
};
 
 
//图结构的描述
class Graph
{
public:
	map<int, Node*> nodes;
	set<Edge*> edges;
 
	Graph()
	{
	}
};
 
//利用边结构描述的图来构建图结构
//[0,7,5]   [from,to,weight]
//[0,1,3]   [from,to,weight]
Graph* createGraph(vector<vector<int>> matrix)
{
	Graph *graph = new Graph();
	int m = matrix.size();
	for(int i=0; i<m; i++)
	{
		int from = matrix[i][0];
		int to = matrix[i][1];
		int weight = matrix[i][2];
		//将起点结构放到图里面
		if(!graph->nodes.count(from))
		{
			Node *fromNode =new Node(from);
			graph->nodes[from] = fromNode;
		}
		//将终点结构放到图里面
		if(!graph->nodes.count(to))
		{
			Node *toNode=new Node(to);
			graph->nodes[to] = toNode;
		}
		//将起点和终点的边结构也放到图里面(点可能已经存在过,边一定是新的)
		Node *fromNode = graph->nodes[from];
		Node *toNode = graph->nodes[to];
		Edge *newEdge = new Edge(fromNode, toNode, weight);
		fromNode->nexts.push_back(toNode);
		fromNode->edges.push_back(newEdge);
		fromNode->out++;
		toNode->in++;
		graph->edges.insert(newEdge);
	}
	return graph;
}


//选一个未选择过的
Node *getMinDistanceAndUnselectedNode(map<Node*,int>distanceMap, set<Node*> touchedNodes)
{
	Node *minNode=nullptr;
	int minDis = INT_MAX;
	for(auto pa: distanceMap)
	{
		Node *node= pa.first;
		int distance = pa.second;
		if(!touchedNodes.count(node) && distance < minDis)
		{
			minNode = node;
			minDis = distance;
		}
	}
	return minNode;
}


//迪杰斯特拉
map<Node*,int> dijstla(Node *from)
{
	set<Node*>vis;
	map<Node*, int>distanceMap;

	distanceMap[from]=0;
	Node *minNode = getMinDistanceAndUnselectedNode(distanceMap, vis);
	while(minNode)
	{
		vis.insert(minNode);
		for(auto edge: minNode->edges)
		{
			Node *toNode = edge->to;
			if(vis.count(toNode))
			{
				distanceMap[toNode]=min(distanceMap[toNode], distanceMap[minNode]+edge->weight);
			}else
			{
				distanceMap[toNode]=distanceMap[minNode]+edge->weight;
			}
		}
		minNode = getMinDistanceAndUnselectedNode(distanceMap, vis);
	}
	return distanceMap;
}