PTA Dijkstra类型题目总结及实现模版

Dijkstra算法简介

• 单源最短路径算法，用于计算一个结点到其他所有节点的最短路径
• 具体原理见Dijkstra算法简介

PTA中的Dijkstra

PTA Dijkstra类型考点分析

• 如何建立图？
  • 题目中结点直接用0-N或1-N的数字表示，则直接建立邻接矩阵保存边即可
  • 题目中如果结点用字符串给出，则需要用map结构来做索引(1087)；或进行简单转换(1072)
• 利用Dijkstra算法求最短路径
  • 只求最短路径的大小和最短路径的数目(1003)
  • 要求输出符合题目要求的具体最短路径
    • 若有多条最短路，输出最大点权的最短路 (1003)
    • 若有多条最短路，输出符合贪心最优解的某个量最大或最小的最短路(1030)
    • 若有多条最短路，输出不符合贪心最优解的某个量最大或最小的最短路。此时需要保存所有最短路，再逐一求出对应量(1030,1087)
  • 多次使用Dijkstra算法求解(1072,1111)

Dijkstra算法的代码实现(C++)

主要使用的数据结构如下：

• 记录各个结点间距离的二维数组:vector<vector<int> > edge

• 记录source和各个结点间的最短距离的数组：vector<int> dist

• 记录各个结点是否被访问过的数组：vector<bool> visited

• 记录源到结点的最短路径的父亲结点 : vector<int> path

  例如假设从源(0)到目的地的路径(4)为 0->3->2->1->4

  则path[0]=-1, path[1]=2, path[2]=3,path[3]=0, path[4]=1

  此处用-1表示源

具体代码实现模版如下：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define inf 0x7fffffff
vector<vector<int> > shortestPath;
void DFS(vector<vector<int> >& path,int index, vector<int> vec){
	if(index==-1){
		reverse(vec.begin(),vec.end());
    shortestPath.push_back(vec);
    return;
  }
  vec.push_back(index);
  for(int i = 0;i<path[index].size();i++){
		DFS(path,path[index][i],vec);
  }
}
int main(){
  	int N; //图中顶点的个数,顶点从0-N
  	int M; //图中边的个数
  	vector<vector<int> > edge(N, vector<int>(N,-1));
  	for(int i = 0;i<M;i++){
			int a,b,weight;
      cin>>a>>b>>weight;
      // 此处以无向图为例
      edge[a][b] = weight;
      edge[b][a] = weight;
    }
  
  	int source;
  	cin>>source;
  	vector<int> visited(N,false);
  	vector<int> dist(N,inf);
  	// vector<int> path(N, -1);
  	vector<vector<int> > path(N);
  	// 初始化source 到自己的距离为0
  	dist[source] = 0;
  	path[source].push_back(-1);
  	//==================开始Dijkstra算法======================
  	for(int i = 0;i<N;i++){
			int index = -1;
      int minDist = inf;
      // 找到距离最短的没有访问过的结点
      for(int j = 0;j<N;j++){
				if(!visited[j] && minDist>dist[j]){
					index = j;
          minDist = dist[j];
        }
      }
      visited[index] = j;
      // 更新最新访问过的结点的相邻结点的距离
      for(int j = 0;j<N;j++){
				if(!visited[j] && edge[index][j]!=-1){
					if(dist[j]>dist[index]+edge[index][j]){
            dist[j] = dist[index]+edge[index][j];
            vector<int> temp(1,index);
            path[j] = temp;
            
          }
          else if(dist[j]==dist[index]+edge[index][j]){
						//根据题目要求填写
            //当存在多条路径时
            /* path[j].push_back(index);*/
          }
        }
      }
    }
  	// 采用DFS得到所有的最短路径
  	vector<int> vec;
  	DFS(path, index,vec);
  	
  	// 输出所有的最短路径
  	for(int i = 0;i<shortestPath.size();i++){
			for(int j = 0;j<shortestPath[i].size();j++){
				cout<<shortestPath[i][j]<<" ";
      }
      cout<<endl;
    }
}

以上为个人学习总结，如有错误欢迎指出！

PTA Dijkstra类型题目总结及实现模版

原文：https://www.cnblogs.com/zxyLeaf/p/PTA_Dijkstra.html