Dijkstra算法簡(jiǎn)介
PTA中的Dijkstra
| 題號(hào) |
題目難點(diǎn)(各題的不同) |
注意事項(xiàng) |
| 1003(25) |
1.求源到目的地最短路的個(gè)數(shù) |
最短路的個(gè)數(shù)不是count[j] = count[index]
而是count[j] += count[index] |
|
2. 輸出最短路中最大的點(diǎn)權(quán)和 |
在路徑的最短距離相等時(shí)，更新權(quán)重
符合貪心的最優(yōu)原則 |
| 1018(30) |
1. 輸出符合題目要求的最短路徑 |
需要使用DFS求具體路徑 |
|
2. 在有多條最短路徑時(shí)按題目要求選擇 |
不符合貪心的最優(yōu)原則 |
| 1030(30) |
1.輸出符合題目要求的最短路徑 |
|
|
2. 在有多條最短路徑時(shí)選擇花費(fèi)最少的路徑 |
符合貪心的最優(yōu)原則，但是需要保存兩個(gè)二維數(shù)組 |
| 1072(30) |
1.處理輸入，將G1...Gn轉(zhuǎn)化為index |
|
|
2. 使用多次Dijkstra算法，
源到不同結(jié)點(diǎn)的最短路并找到最短路的最大值 |
|
| 1087(30) |
1. 使用map來(lái)為城市名字建立index
使用另一個(gè)map保存index和城市名的關(guān)系 |
|
|
2. 輸出擁有最大點(diǎn)權(quán)的最短路徑 |
|
|
3. 若路徑不唯一輸出，最短路徑中平均點(diǎn)權(quán)最大的路徑 |
不符合貪心的最優(yōu)原則 |
| 1111(30) |
1. 使用兩次Dijkstra算法，得到最短路徑和耗時(shí)最少的路徑 |
|
|
2. 輸出最短路徑和耗時(shí)最少路徑 |
|
PTA Dijkstra類(lèi)型考點(diǎn)分析
- 如何建立圖？
- 題目中結(jié)點(diǎn)直接用0-N或1-N的數(shù)字表示，則直接建立鄰接矩陣保存邊即可
- 題目中如果結(jié)點(diǎn)用字符串給出，則需要用map結(jié)構(gòu)來(lái)做索引(1087)；或進(jìn)行簡(jiǎn)單轉(zhuǎn)換(1072)
- 利用Dijkstra算法求最短路徑
- 只求最短路徑的大小和最短路徑的數(shù)目(1003)
- 要求輸出符合題目要求的具體最短路徑
- 若有多條最短路，輸出最大點(diǎn)權(quán)的最短路 (1003)
- 若有多條最短路，輸出符合貪心最優(yōu)解的某個(gè)量最大或最小的最短路(1030)
- 若有多條最短路，輸出不符合貪心最優(yōu)解的某個(gè)量最大或最小的最短路。此時(shí)需要保存所有最短路，再逐一求出對(duì)應(yīng)量(1030,1087)
- 多次使用Dijkstra算法求解(1072,1111)
Dijkstra算法的代碼實(shí)現(xiàn)(C++)
主要使用的數(shù)據(jù)結(jié)構(gòu)如下：
-
記錄各個(gè)結(jié)點(diǎn)間距離的二維數(shù)組:vector<vector<int> > edge
-
記錄source和各個(gè)結(jié)點(diǎn)間的最短距離的數(shù)組：vector<int> dist
-
記錄各個(gè)結(jié)點(diǎn)是否被訪問(wèn)過(guò)的數(shù)組：vector<bool> visited
-
記錄源到結(jié)點(diǎn)的最短路徑的父親結(jié)點(diǎn) : vector<int> path
例如假設(shè)從源(0)到目的地的路徑(4)為 0->3->2->1->4
則path[0]=-1, path[1]=2, path[2]=3,path[3]=0, path[4]=1
此處用-1表示源
具體代碼實(shí)現(xiàn)模版如下：
#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; //圖中頂點(diǎn)的個(gè)數(shù),頂點(diǎn)從0-N
int M; //圖中邊的個(gè)數(shù)
vector<vector<int> > edge(N, vector<int>(N,-1));
for(int i = 0;i<M;i++){
int a,b,weight;
cin>>a>>b>>weight;
// 此處以無(wú)向圖為例
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);
//==================開(kāi)始Dijkstra算法======================
for(int i = 0;i<N;i++){
int index = -1;
int minDist = inf;
// 找到距離最短的沒(méi)有訪問(wèn)過(guò)的結(jié)點(diǎn)
for(int j = 0;j<N;j++){
if(!visited[j] && minDist>dist[j]){
index = j;
minDist = dist[j];
}
}
visited[index] = j;
// 更新最新訪問(wèn)過(guò)的結(jié)點(diǎn)的相鄰結(jié)點(diǎn)的距離
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]){
//根據(jù)題目要求填寫(xiě)
//當(dāng)存在多條路徑時(shí)
/* 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;
}
}
以上為個(gè)人學(xué)習(xí)總結(jié)，如有錯(cuò)誤歡迎指出！
|
