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

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

way：用加强堆来实现每回pop出distance最小的节点，那么distance就是堆中元素移动的依据了，addOrupdateOrIgnore的过程中更新 老节点的distance意味着这个节点处的值变小了（distance要往小了变），就要heapInsert向上浮动，如果是新节点有了distance，就要将新节点添加到堆尾再去heapInsert，indexMap[a] = -1表示节点a进入过小根堆并被弹出了，在后续的选择中可以过滤掉被弹出选择过的节点，只考虑还在堆里或还没进过小根堆的节点。（为什么用堆，因为有每回pop出distance最小的节点的需求，为什么是加强堆，因为堆中节点的值会变化，变化后需要resign节点在堆中的位置再去pop出最小值，而普通的堆只能在一开始的时候放入元素列表，然后依次pop出最小值。）

#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;
}


class NodeMinHeap
{
private:
	vector<Node *>heap;
	map<Node*, int>indexMap;
	map<Node*, int>distanceMap;
	int heapSize;
public:
	NodeMinHeap()
	{
		heapSize = 0;
	}

	bool isEmpty()
	{
		return heapSize==0;
	}

	bool isEntered(Node *node)
	{
		//进入过，也有可能出去了
		return indexMap.count(node);
	}

	bool isInHeap(Node *node)
	{
		//进入过，还没出去的，还在的
		return isEntered(node) && indexMap[node]!=-1;
	}

	void swap(int i, int j)
	{
		Node *a = heap[i];
		Node *b = heap[j];
		indexMap[a]=j;
		indexMap[b]=i;
		heap[i]=b;
		heap[j]=a;
	}

	//没有用单纯的push方法
	//有一个node节点，现在发现了一个从源点到node的距离为distance的距离
	//判断要不要更新，如果是老节点就更新，否则就push
	void pushOrUpdateOrIngore(Node *node, int distance)
	{
		if(isInHeap(node))           //进入过还在的
		{
            //update
			distanceMap[node]=min(distanceMap[node], distance);
			heapInsert(indexMap[node]);
		}else if(!isEntered(node))   //没进入过的（else的可能是没进入过的，可能是进入了出去的）
		{
            //push
			heap.push_back(node);
			heapSize++;
			indexMap[node]=heapSize-1;
			distanceMap[node]=distance;
			heapInsert(heapSize-1);
		}
        //ignore
	}

	bool comp(int i, int j)
	{
		Node *a = heap[i];
		Node *b = heap[j];
		return distanceMap[a]<distanceMap[b];
	}

	void heapInsert(int index)
	{
		int fa=(index-1)/2;
		while(comp(index, fa))
		{
			swap(index, fa);
			index = fa;
			fa =(index-1)/2;
		}
	}


	//弹出小根堆堆顶元素
	NodeRecord pop()
	{
		Node *top = heap[0];
		NodeRecord result(top, distanceMap[top]);
		//swap,要删除的元素在堆尾，堆尾的元素在0位置处(堆尾的元素本来是无辜的）
		swap(0, heapSize-1);
		//先处理堆尾要删除的元素top
		heap.pop_back();
		//用indexMap[a]=-1来表示进入过但是出去了的节点
		indexMap[top]=-1;
		distanceMap.erase(top);
		heapSize--;
		//再处理0位置处元素
		heapify(0);
		return result;
	}

	void heapify(int index)
	{
		int left = 2*index+1;
		while(left< heapSize)
		{
			int minChild = (left+1<heapSize && comp(left+1, left))?left+1:left;
			if(comp(index, minChild))
			{
				break;
			}
			swap(index, minChild);
			index = minChild;
			left = 2*index+1;
		}
	}

};


struct NodeRecord
{
	Node *node;
	int distance;

	NodeRecord(Node *node, int distance)
	{
		this->node = node;
		this->distance = distance;
	}
};


//从源点from出发，所有from能到达的节点，生成到达每个节点的最小路径记录并返回
map<Node *, int> dijstla2(Node *from)
{
	map<Node*, int>disResultMap;
	NodeMinHeap heap;
	heap.pushOrUpdateOrIngore(from, 0);
	while(!heap.isEmpty())
	{
		NodeRecord record = heap.pop();
		Node *node = record.node;
		int distance = record.distance;
		disResultMap[node]=distance;
		//更新未选择过的新老节点的distance
		for(auto edge: node->edges)
		{
			heap.pushOrUpdateOrIngore(edge->to, distance+edge->weight);
		}
	}
	return disResultMap;
}

对比着看 图的迪杰斯特拉算法1（有向、无负权值的图）-CSDN博客 和这个 加强堆（大根堆）-CSDN博客

有什么问题后面再看吧，总是要在实践中验证这些的。