Dijkstra算法簡介

• 單源最短路徑算法，用于計算一個結點到其他所有節(jié)點的最短路徑
• 具體原理見Dijkstra算法簡介

PTA中的Dijkstra

PTA Dijkstra類型考點分析

• 如何建立圖？
  • 題目中結點直接用0-N或1-N的數(shù)字表示，則直接建立鄰接矩陣保存邊即可
  • 題目中如果結點用字符串給出，則需要用map結構來做索引(1087)；或進行簡單轉換(1072)
• 利用Dijkstra算法求最短路徑
  • 只求最短路徑的大小和最短路徑的數(shù)目(1003)
  • 要求輸出符合題目要求的具體最短路徑
    • 若有多條最短路，輸出最大點權的最短路 (1003)
    • 若有多條最短路，輸出符合貪心最優(yōu)解的某個量最大或最小的最短路(1030)
    • 若有多條最短路，輸出不符合貪心最優(yōu)解的某個量最大或最小的最短路。此時需要保存所有最短路，再逐一求出對應量(1030,1087)
  • 多次使用Dijkstra算法求解(1072,1111)

Dijkstra算法的代碼實現(xiàn)(C++)

主要使用的數(shù)據(jù)結構如下：

• 記錄各個結點間距離的二維數(shù)組:vector<vector<int> > edge

• 記錄source和各個結點間的最短距離的數(shù)組：vector<int> dist

• 記錄各個結點是否被訪問過的數(shù)組：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表示源

具體代碼實現(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; //圖中頂點的個數(shù),頂點從0-N
  	int M; //圖中邊的個數(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;
      // 此處以無向圖為例
      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]){
						//根據(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;
    }
}

以上為個人學習總結，如有錯誤歡迎指出！