给定带权有向图G＝(V，E)，其中每条边的权是非负实数。给定V中的一个顶点，称为源。 现在要计算从源到所有其它各顶点的最短路长度，这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。 每条边上标注有字母和数字，在字母旁边的数字为路长。
算法从优先队列中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。 剪枝规则： 如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。 算法从优先队列中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。 如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。
#include <iostream> #include <string> #include <queue> using namespace std; class Graphic{ int n;//图中顶点的个数 int e;//边的数目 int **adjmatrix;//邻接矩阵，存储图 int *dist;//dist[n],存储单元点到其他n-1个顶点的最短路的长度 int *prev;//prev[i]=j 存储顶点i 的前驱结点为j , 利用这些前驱结点可以找到源点到顶点i的最短路 int start;//源点 public: Graphic(int n, int e); void ShortPath(); void display(); }; class PathNode{ //放入优先队列中的节点,解空间中的结点 int i; //解空间中结点的编号。一个结点对应于一条路 int length;//路的长度。 friend class Graphic; public: PathNode(int a=0, int b=0):i(a),length(b){} bool operator <(PathNode b) const {//定义优先关系函数 return length>b.length; } }; Graphic::Graphic(int n, int e){ this->n=n; this->e=e; adjmatrix=new int*[n+1]; dist=new int[n+1]; prev=new int[n+1]; for(int i=1;i<=n;i++) adjmatrix[i]=new int[n+1]; cout<<"输入源点编号："; cin>>start; cout<<"请输入e条边"<<endl; for(i=1;i<=n;i++){ //邻接矩阵初始化 for(int j=1;j<=n;j++) adjmatrix[i][j]=-1; //两个顶点之间没有边 adjmatrix[i][i]=0; } for( i=0;i<e;i++) { int a, b,length; cin>>a>>b>>length; //输入一条边所依附的两个顶点和这条边的长度 adjmatrix[a][b]=length; //有向图 dist[i]=99999; //最短路赋初值 prev[i]=start; } }; void Graphic::ShortPath() { priority_queue<PathNode> q; PathNode first,next; first.i=start; //计算顶点v到其它顶点的最短路 first.length=0; prev[start]=0; dist[start]=0; q.push(first); while(true) { if(q.empty()) break; first=q.top(); q.pop(); for(int i=1;i<=n;i++){// 搜索孩子结点，并将可行的结点插入优先队列 if(adjmatrix[first.i][i]>0 && (first.length+adjmatrix[first.i][i])<dist[i]){ dist[i]=first.length+adjmatrix[first.i][i]; prev[i]=first.i; next.i=i; next.length=dist[i]; q.push(next); } } } } void Graphic::display(){ for (int i=1;i<=n;i++) { cout<<"源点1 到顶点"<<i<<"的最短路长度为"<<dist[i]<<"如下："; int j; j=i; cout<<j; while(j) { cout<<"->"<<prev[j]; j=prev[j]; } cout<<endl; } } int main(){ int n,e; cin>>n>>e; Graphic g(n,e); g.ShortPath(); g.display(); return 0; }