最短路径问题--迪杰斯特拉（Dijkstra）算法

#include <iostream>
#include <string>
#include <vector>
#include <iomanip>
#define INF 999999999.9
using namespace std;
vector<float>Dijkstra(vector<vector<float>>&graph, int start);

int main()
{
    string nodes[6] = {"北京","天津","郑州","济南","长沙","海口"};
    int n = 6; //顶点数// 0北京，1天津，2郑州，3济南，4长沙，5海口
    vector<vector<float>>graph;//样例中对于的邻接矩阵

    for(int i=0;i<n;i++){
        graph.push_back(vector<float>());
        for(int j=0;j<n;j++){
            graph[i].push_back(INF);
        }
        graph[i][i] = 0.0;
    }
    graph[0][1]=100.0;//北京 到 天津
    graph[1][0]=100.0;
    graph[1][2]=900.0;//天津 到 郑州
    graph[2][1]=900.0;
    graph[1][3]=300.0;//天津 到 济南
    graph[3][1]=300.0;
    graph[2][3]=400.0;//郑州到 济南
    graph[3][2]=400.0;
    graph[2][4]=500.0;//郑州 到 长沙
    graph[4][2]=500.0;
    graph[3][4]=1300.0;//济南 到 长沙
    graph[4][3]=1300.0;
    graph[4][5]=1500.0;//长沙 到 海口
    graph[5][4]=1500.0;
    graph[3][5]=1400.0;//济南 到 海口
    graph[5][3]=1400.0;
    
    cout<<"邻接矩阵："<<endl;
    cout<<setw(5)<<right<<"距离"<<" ";//打印时宽度设为5，右对齐
    for(int i=0;i<n;i++){
        cout<<setw(5)<<right<<nodes[i]<<" ";//打印时宽度设为5，右对齐
    }
    cout<<endl;
    for(int i=0;i<n;i++){
        cout<<setw(5)<<right<<nodes[i]<<" ";//打印时宽度设为5，右对齐
        for(int j=0;j<n;j++){
            cout<<setw(5)<<right<<graph[i][j]<<" ";//打印时宽度设为5，右对齐
        }
        cout<<endl;
    }
    cout<<endl;
    cout<<"北京（节点0）到其它节点的最短距离："<<endl;
    vector<float> dist = Dijkstra(graph,0);
    for(int i=0; i<n;i++){
        if(i!=0) cout<<nodes[0]<<"到"<<nodes[i]<<"："<<dist[i]<<endl;
    }
    cout<<endl;
    cout<<"郑州（节点2）到其它节点的最短距离："<<endl;
    dist = Dijkstra(graph,2);
    for(int i=0; i<n;i++){
        if(i!=2) cout<<nodes[2]<<"到"<<nodes[i]<<"："<<dist[i]<<endl;
    }
    return 0;
}

vector<float>Dijkstra(vector<vector<float>>&graph, int start){
    //start 为起点的索引
    int n = graph.size(); //顶点个数
    vector<bool> visit(n); //已完成访问的节点
    vector<float> dist(n);//存储从起点start到其它顶点的最短路径
    for(int i=0;i<n;i++){
        dist[i] = graph[start][i];//将minDist数组初始化为最初图中的路径长度
    }
    visit[start] = true;//标记其实顶点为已访问
    for(int i=0;i<n;i++){
        float min_dist = INF;//存储从起点到其它未被访问节点中的最短距离
        int middle = 0;//存储最短距离的编号

        for(int j=0;j<n;j++){
            //如果顶点j未被访问，且dist[j] < min_dist
            if(visit[j] == false && dist[j] < min_dist){
                min_dist = dist[j];//更新最短距离为dist[j]
                middle = j;//更新中间节点编号为j
            }
        }
        //以新的middle 为中间节点，循环遍历其它所有节点
        for(int j =0; j<n; j++){
            float sum = dist[middle]+graph[middle][j];//从起始节点到middle 与从middle到节点j的距离之和
            //
            if(visit[j]==false && dist[j] > sum){
                dist[j] = sum;//更新距离为从起始节点到middle与从middle到节点j的距离之和
            }
        }
        visit[middle] = true;//节点middle 标记为已访问
    }
    return dist;//返回最短路径结果数组
}