#include<iostream> #include<vector> #include<iterator> #include<limits.h> #include<string> using namespace std; int n; //顶点个数 vector<vector<int> >g; //g：图（graph）（用邻接矩阵（adjacent matrix）表示） int s; //s：源点（source） vector<bool>known; //known：各点是否知道最短路径 vector<int>dist; //dist：源点 s 到各点的最短路径长度 vector<int>pre; //prev 各点的最短路径的前一顶点 void Dijkstra() { //贪心算法 known.assign(n,false); dist.assign(n,INT_MAX); pre.resize(n); //初始化 known、dist、prev dist[s]=0; //初始化源点 s 到自身的路径 for(;;) { int min=INT_MAX,v=s; for(int i=0; i<n; ++i) if(!known[i]&&min>dist[i]) min=dist[i],v=i; //寻找未知的最短路径的顶点 v if(min==INT_MAX)break; //如果找不到，退出 known[v]=true; for(int w=0; w<n; ++w) //遍历所有 v 指向的顶点 w if(!known[w]&&g[v][w]<INT_MAX && dist[w]>dist[v]+g[v][w]) //调整顶点 w 的最短路径长度 dist 和最短路径的前一顶点 prev dist[w]=dist[v]+g[v][w],pre[w]=v; } } void Print_SP(int v) { if(v!=s)Print_SP(pre[v]); cout<<v<<" "; } int main() { n=5; g.assign(n,vector<int>(n,INT_MAX)); //构建图 g[0][1]=10; g[0][3]=30; g[0][4]=100; g[1][2]=50; g[2][4]=10; g[3][2]=20; g[3][4]=60; s=0; Dijkstra(); copy(dist.begin(),dist.end(),ostream_iterator<int>(cout," ")); cout<<endl; for(int i=0; i<n; ++i) if(dist[i]!=INT_MAX) { cout<<s<<"->"<<i<<":"; Print_SP(i); cout<<endl; } return 0; }每行代码什么意思

这段代码实现了Dijkstra算法，用于求解带权图中单源最短路径问题。下面是每行代码的具体意思：

#include<iostream> 
#include<vector> 
#include<iterator> 
#include<limits.h> 
#include<string> 

头文件的引入。

using namespace std; 

使用标准命名空间。

int n; //顶点个数 
vector<vector<int> >g; //g：图（graph）（用邻接矩阵（adjacent matrix）表示） 
int s; //s：源点（source） 
vector<bool>known; //known：各点是否知道最短路径 
vector<int>dist; //dist：源点 s 到各点的最短路径长度 
vector<int>pre; //prev 各点的最短路径的前一顶点 

定义了顶点个数、图、源点、各点是否知道最短路径、源点到各点的最短路径长度、各点的最短路径前一顶点等变量。

void Dijkstra() { //贪心算法 
    known.assign(n,false); 
    dist.assign(n,INT_MAX); 
    pre.resize(n); //初始化 known、dist、prev 
    dist[s]=0; //初始化源点 s 到自身的路径 
    for(;;) { 
        int min=INT_MAX,v=s; 
        for(int i=0; i<n; ++i) 
            if(!known[i]&&min>dist[i]) 
                min=dist[i],v=i; //寻找未知的最短路径的顶点 v 
        if(min==INT_MAX)break; //如果找不到，退出 
        known[v]=true; 
        for(int w=0; w<n; ++w) //遍历所有 v 指向的顶点 w 
            if(!known[w]&&g[v][w]<INT_MAX && dist[w]>dist[v]+g[v][w]) //调整顶点 w 的最短路径长度 dist 和最短路径的前一顶点 prev 
                dist[w]=dist[v]+g[v][w],pre[w]=v; 
    } 
} 

Dijkstra算法函数的实现。首先对known、dist、prev进行初始化，然后进行循环，每次找到未知的最短路径的顶点v，将其标记为已知，再遍历所有v指向的顶点w，调整顶点w的最短路径长度和最短路径的前一顶点prev。

void Print_SP(int v) { 
    if(v!=s)Print_SP(pre[v]); 
    cout<<v<<" "; 
} 

输出最短路径的函数实现。递归输出前一顶点的最短路径，然后输出当前顶点v。

int main() { 
    n=5; 
    g.assign(n,vector<int>(n,INT_MAX)); //构建图 
    g[0][1]=10; 
    g[0][3]=30; 
    g[0][4]=100; 
    g[1][2]=50; 
    g[2][4]=10; 
    g[3][2]=20; 
    g[3][4]=60; 
    s=0; 
    Dijkstra(); 
    copy(dist.begin(),dist.end(),ostream_iterator<int>(cout," ")); 
    cout<<endl; 
    for(int i=0; i<n; ++i) 
        if(dist[i]!=INT_MAX) { 
            cout<<s<<"->"<<i<<":"; 
            Print_SP(i); 
            cout<<endl; 
        } 
    return 0; 
} 

主函数的实现。初始化图，设置源点，调用Dijkstra函数求解最短路径，输出源点到各点的最短路径长度，逐个输出源点到每个顶点的最短路径及其长度。