Dijkstra算法

简单介绍

1. 首先，我们要对单源最短路径有个基本的认识，这是前提条件；
2. 给出简单的介绍：
   

Dijkstra算法的实现方法

算法思想

1. 找到起点到各个未访问过的顶点（包括自身）的距离最小的点u并访问顶点u；（起初，设置起点到其余各个顶点的距离为无穷大，到自身的距离为0）
2. 遍历未访问过的结点v，查看经过结点u是否可以使起点到结点v距离变小，如果可以，则更新起点到结点v的最小距离；
3. 重复1,2步骤n次（n为所有结点的总个数）

伪代码

扩展-若到顶点v的最短路径有多条

则必然会在题目中添加有其他的附加属性–例如：经过某条路径的时间、顶点V添加权重、或者直接求最短路径的条数等；
遇到这类问题，直接在需要优化最短路径时添加对应代码，例如先以路径最短为优先，当路径相同时即$shortestPath[u]+lengthOfRoad[u][v]==shortestPath[v]$shortestPath[u]+lengthOfRoad[u][v]==shortestPath[v]时，再进行下一步判断；例如更新最短路径的的条数$countOfPath[v]=countOfPath[u]+countOfPath[v]$countOfPath[v]=countOfPath[u]+countOfPath[v].

如果需要输出最短路径经过的各个顶点

同样与上一个小节一致，在需要优化最短路径时（即若经过u到达v的距离更短），记录v的前驱结点u，并记作pre[v]=u;
然后递归的输出路径，以下给出C++的代码：

最后给出一道题目，并用C++给出具体的实现：

例题

C++代码：

#include<cstdio>
#include<algorithm>
using namespace std;
#define debug 1
#define max 1000000000
using namespace std;
int lengthOfRoad[500][500];
//void dijkstra(int source,int destination,int cityNumber,int roadNumber,int teamOfCity[],int countOfPath[],int shortestPath[],int handsNumber[]) {
void dijkstra(int source,int destination,int cityNumber,int roadNumber,int teamOfCity[],int countOfPath[],int shortestPath[],int handsNumber[]) {
	bool visited[cityNumber]= {false};
	for(int i=0; i<cityNumber; i++) {//找到源点到所有顶点的最短距离
		int u=-1,MIN=max;
		for(int j=0; j<cityNumber; j++) {//找到最短距离的未访问的定点
			if(visited[j]==false&&shortestPath[j]<MIN) {
				u=j;
				MIN=shortestPath[j];
			}
		}
		if(u==-1)return;//顶点不可达
		visited[u]=true;//访问该顶点
		for(int v=0; v<cityNumber; v++) {//检查经过顶点u到达的其余未访问的定点v中距离是否更短，是，则优化顶点v的最短距离
			if(visited[v]==false&&lengthOfRoad[u][v]!=max) {//注意这里一定要先判断是否访问过该节点并且u与v之间是否有路径
				if(shortestPath[u]+lengthOfRoad[u][v]<shortestPath[v]) {//优化最短距离
					shortestPath[v]=shortestPath[u]+lengthOfRoad[u][v];
					countOfPath[v]=countOfPath[u];//记录路径数
					handsNumber[v]=handsNumber[u]+teamOfCity[v];//记录路径权重
				} else if(shortestPath[u]+lengthOfRoad[u][v]==shortestPath[v]) {//如果路径距离相等
					countOfPath[v]=countOfPath[u]+countOfPath[v];//增加路径数
					if(handsNumber[u]+teamOfCity[v]>handsNumber[v]) {//找到最大路径权重
						handsNumber[v]=handsNumber[u]+teamOfCity[v];
					}
				}
			}
		}
	}
}
int main() {
//构建代码手脚架
#if debug
	freopen("_in.txt","r",stdin);//输入重定向
#endif
	//城市数量、道路条数、所在地、目的地
	int cityNumber,roadNumber,source, destination;
	scanf("%d%d%d%d",&cityNumber,&roadNumber,&source,&destination);
	//每个城市驻扎队伍
	int teamOfCity[cityNumber];
	for(int i=0; i<cityNumber; i++) {
		scanf("%d",&teamOfCity[i]);
	}
	//道路连接的城市以及道路长度
	for(int i=0; i<cityNumber; i++) {
		fill(lengthOfRoad[i],lengthOfRoad[i]+cityNumber,max);
	}
	for(int i=0; i<roadNumber; i++) {
		int sou,des,length;
		scanf("%d%d%d",&sou,&des,&length);
		lengthOfRoad[sou][des]=length;
		lengthOfRoad[des][sou]=length;
	}
	int countOfPath[cityNumber];
	//初始化数据
	fill(countOfPath,countOfPath+cityNumber,0);
	countOfPath[source]=1;
	int shortestPath[cityNumber];//统计从所在地到各个城市的最短距离
	fill(shortestPath,shortestPath+cityNumber,max);
	shortestPath[source]=0;
	int handsNumber[cityNumber]= {0}; //统计从所在地到目的地可调动的最多队伍
	handsNumber[source]=teamOfCity[source];
    //寻找最短路径
	dijkstra(source,destination,cityNumber,roadNumber,teamOfCity,countOfPath,shortestPath,handsNumber) ;
	printf("%d %d\n",countOfPath[destination],handsNumber[destination]);
	return 0;
}

输入样例

5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 2
2 4 1
3 4 1

结果

end