Dijkstra算法简介
PTA中的Dijkstra
| 题号 |
题目难点(各题的不同) |
注意事项 |
| 1003(25) |
1.求源到目的地最短路的个数 |
最短路的个数不是count[j] = count[index]
而是count[j] += count[index] |
|
2. 输出最短路中最大的点权和 |
在路径的最短距离相等时，更新权重
符合贪心的最优原则 |
| 1018(30) |
1. 输出符合题目要求的最短路径 |
需要使用DFS求具体路径 |
|
2. 在有多条最短路径时按题目要求选择 |
不符合贪心的最优原则 |
| 1030(30) |
1.输出符合题目要求的最短路径 |
|
|
2. 在有多条最短路径时选择花费最少的路径 |
符合贪心的最优原则，但是需要保存两个二维数组 |
| 1072(30) |
1.处理输入，将G1...Gn转化为index |
|
|
2. 使用多次Dijkstra算法，
源到不同结点的最短路并找到最短路的最大值 |
|
| 1087(30) |
1. 使用map来为城市名字建立index
使用另一个map保存index和城市名的关系 |
|
|
2. 输出拥有最大点权的最短路径 |
|
|
3. 若路径不唯一输出，最短路径中平均点权最大的路径 |
不符合贪心的最优原则 |
| 1111(30) |
1. 使用两次Dijkstra算法，得到最短路径和耗时最少的路径 |
|
|
2. 输出最短路径和耗时最少路径 |
|
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;
}
}
以上为个人学习总结，如有错误欢迎指出！
|
