【算法设计与分析】 单源最短路径（贪心算法） Dijkstra
【问题描述】
Dijkstra算法解决的是带权重的有向图上单源最短路径问题。所有边的权重都为非负值。设置顶点集合S并不断地作贪心选择来扩充这个集合。使用最小堆数据结构构造优先队列。第1个顶点为源。
【输入形式】
在屏幕上输入顶点个数和连接顶点间的边的权矩阵。
【输出形式】
从源到各个顶点的最短距离及路径。
【样例输入】
50 10 0 30 1000 0 50 0 00 0 0 0 100 0 20 0 600 0 0 0 0
【样例输出】
10: 1->250: 1->4->330: 1->460: 1->4->3->5
【样例说明】
输入：顶点个数为5。连接顶点间边的权矩阵大小为5行5列，位置[i,j]上元素值表示第i个顶点到第j个顶点的距离，0表示两个顶点间没有边连接。
输出：每行表示源1到其余各顶点的最短距离及路径，冒号后有一空格。如果源1到该顶点没有路，则输出：“inf: 1->u”，其中u为该顶点编号。
【题解代码】
#include <iostream>#include <cstdio>#include <queue>#include <stack>using namespace std;const int INF=0x3f3f3f3f;//无穷大 int n,g[105][105],dis[105],pre[105],vis[105];struct edge{int u,v,d;//边的起点、终点、权值 bool operator < (const edge &a) const{return d>a.d;}};int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){cin>>g[i][j];if(g[i][j]==0)g[i][j]=INF;}priority_queue<edge> q;//优先队列 int temp=1,cnt=0;//当前顶点和边数 for(int i=1;i<=n;i++){if(i!=temp){pre[i]=temp;dis[i]=g[temp][i];q.push({temp,i,g[temp][i]});}}//从结点temp开始，此题为从结点1开始 while(!q.empty()){edge t=q.top();q.pop();int v=t.v;if(vis[v]) continue;//已经在已加入点的集合当中 vis[v]=1;cnt++;if(cnt==n-1) break;temp=v;for(int i=1;i<=n;i++){if(!vis[i]&&dis[temp]+g[temp][i]<dis[i]){dis[i]=dis[temp]+g[temp][i];pre[i]=temp;q.push({temp,i,dis[temp]+g[temp][i]});}}//更新优先队列 }for(int i=2;i<=n;i++){if(dis[i]==INF){cout<<"inf: 1->"<<i<<endl;continue;}//如果源1到该顶点没有路，则输出："inf: 1->u" stack<int> s;int t=i;while(t!=0){s.push(t);t=pre[t];}cout<<dis[i]<<": "<<s.top();s.pop();while(!s.empty()){cout<<"->"<<s.top();s.pop();}cout<<endl;}//输出结果 return 0;}
