Djkstra最短路径算法的c++代码实现

Djkstra算法是求解单源（起始点固定）最短路径问题的一种经典方法，它采用了贪心策略（其实我觉得也是动态规划），可以求得图中的一个点到其他所有点的距离，计算复杂度是 O(E|V|)，如果采用最小堆优化可以达到O(ElogV )。算法的整体思想是将顶点分成两类：已经构成最短路的点的集合V1和没有构成最短路的点的集合V2。我们将dist[i]设置为第 i个点到V1的距离，每次将V2中取距离V1集合最短的点P放入V1中，同时因为P被放入了V1，那么其他点到V1的最短路就有可能通过P了，所以我们更新所有集合V2内的点j到V1的距离dist[j] = min( dist[j], dist[i_P] + G[i_P][j] )，其中i_P表示P的下标， G[i_P][j] 表示图中P到j的距离。但是需要注意一点：Djkstra算法不能解决具有负权边的最短路径问题。显然，当具有负权边的时候你无法保证每次放入V1的都是最短路径， 具体可以参考点击打开链接，讲的很清楚。我们以下图为例编写代码，图的左边是最短路的真实结果，右边是图

#include <iostream>
#include<vector>
#include<queue>
using namespace std;
 
#define MAX_PATH 999999
 
int shortestId( const vector<int>& dist, const vector<bool>& isShortest ) //寻找当前未放入最短路径集合的所有ID中路径最短的ID号
{
 int min_dist = MAX_PATH;
 int min_ID = -1;
 for(int i = 0; i < dist.size() ; i++)
 {
 if(false == isShortest[i]){
 if(dist[i] < min_dist){
 min_dist = dist[i];
 min_ID = i;
 }
 }
 }
 return min_ID;
}
vector<int> Djkstra( const vector<vector<int> >& Graph)
{
 int num_vertex = Graph.size();
 vector<bool> isShortest( num_vertex, false); //初始化只有第一个顶点（index = 0）被放入最短路的ID集合中
 isShortest[0] = true;
 vector<int> dist(num_vertex, MAX_PATH); //dist[i]表示当前节点 i+1(下标i)到最短路的id集合中所有点的最短距离
 dist[0] = 0;
 
 for(int i = 1 ;i < num_vertex; i++)
 {
 if(Graph[0][i] <MAX_PATH) //初始化dist，所有不与1号节点（下标0）相连的设置为正无穷
 dist[i] = Graph[0][i];
 }
 for(int i = 0; i < num_vertex - 1; i++){
 int id = shortestId(dist, isShortest); //在所有非最短路的点集合中找到距离最短路集合最近的点，放入最短路集合
 isShortest[id] = true;
 for(int j = 0; j < num_vertex; j++){ //将 id放入最短路集合后，更新所有集合外的元素的距离，他们有可能有通过id的更短路
 if( !isShortest[j] ){
 dist[j] = min(dist[j], dist[id] + Graph[id][j]);
 }
 }
 }
 return dist;
}
void addEdge( const int& startP, const int& endP, const int& weight ,vector<vector<int> >& Graph)
{
 Graph[startP][endP] = weight;
 //Graph[endP][startP] = weight;
}
 
int main()
{
 vector<vector<int> > Graph(6, vector<int>(6, MAX_PATH) );
 addEdge(0,1,10 ,Graph);
 addEdge(0,5,3 ,Graph);
 addEdge(1,2,7 ,Graph);
 addEdge(1,3,5 ,Graph);
 addEdge(3,0,3,Graph);
 addEdge(3,2,4,Graph);
 addEdge(3,4,7,Graph);
 addEdge(5,1,2,Graph);
 addEdge(5,3,6,Graph);
 addEdge(5,4,1,Graph);
 /* for(int i =0 ; i < Graph.size(); i++)
 {
 for(int j = 0; j < Graph.size(); j++)
 cout << Graph[i][j] << "\t";
 cout <<endl;
 }*/
 vector<int> shortestDist = Djkstra(Graph);
 for(int i = 0; i <shortestDist.size(); i++)
 cout <<shortestDist[i] << endl;
 return 0;
}

最后，如果你想学C/C++可以私信小编“01”获取素材资料以及开发工具和听课权限哦！