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;
}
           

实验结果如下，可以看到我们求得的最短路的结果就是上图中左边的表示