连续T组数据输入，每组输入数据的第一行给出四个正整数N,M，s，d，其中N(2 <= N <= 500)是城市数目，城市编号从0～N-1，M是城市间高速公路的条数，s是出发地的城市编号，d是目的地的城市编号；随后M行，每行给出一条高速公路的信息，表示城市1、城市2、高速公路长度、收费额，中间以空格间隔，数字均为整数且不超过500，输入数据均保证有解。
在同一行中输出路径长度和收费总额，数据间用空格间隔。
最短路径：
Dijkstra(迪杰斯特拉)算法：是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
算法思想：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
算法步骤：
a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则<u,v>正常有权值，若u不是v的出边邻接点，则<u,v>权值为∞。
b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
d.重复步骤b和c直到所有顶点都包含在S中。
#include<iostream> #include<queue> #include<limits.h> #include<cstring> #define Max INT_MAX using namespace std; int Edge[100][100]; int dist[100]; //原点v0到vi最短路径长度 int path[100]; //前一序号节点 void Dijkstra(int n,int v0,int vn) { int s[100]; //标记数组 for(int i=0; i<n; i++) //初始化dist数组和path数组 { dist[i]=Edge[v0][i]; if(i!=v0&&dist[i]<Max) path[i]=v0; else path[i]=-1; } memset(s,0,sizeof(s)); //清零 s[v0]=1; dist[v0]=0; for(int i=1; i<n; i++) { int Min=Max; int k=v0; for(int j=0; j<n; j++) //选择当前集合中最短路径的顶点k if(!s[j]&&dist[j]<Min) { Min=dist[j]; k=j; } s[k]=1; for(int j=0; j<n; j++) if(!s[j]&&Edge[k][j]<Max&&dist[k]+Edge[k][j]<dist[j]) { dist[j]=dist[k]+Edge[k][j]; path[j]=k; } } } int main() { int t; cin>>t; while(t--) { int n,m,s,d; cin>>n>>m>>s>>d; for(int i=0; i<n; i++) //初始化邻接矩阵 for(int j=0; j<n; j++) if(i==j) Edge[i][j]=0; else Edge[i][j]=Max; for(int i=0; i<m; i++) { int a,b,l,c; cin>>a>>b>>l; Edge[a][b]=l; } Dijkstra(n,s,d); int so[100]; cout<<endl; for(int i=1; i<n; i++) { cout<<dist[i]<<"\t"; memset(so,0,sizeof(so)); int k=0; so[k]=i; while(path[so[k]]!=0) { k++; so[k]=path[so[k-1]]; } k++; so[k]=0; for(int j=k; j>0; j--) cout<<so[j]<<"->"; cout<<so[0]<<endl; } } return 0; }下面是测试数据：
本题要求不一样，稍微改动一下：
#include<iostream> #include<queue> #include<limits.h> #include<cstring> #define Max INT_MAX #define MaxE 510 using namespace std; int Edge[MaxE][MaxE]; int cost[MaxE][MaxE]; void Dijkstra(int n,int v0,int vn) { int dist[MaxE]; //原点v0到vi最短路径长度 int s[MaxE]; //标记数组 int mon[MaxE]; // int path[MaxE]; //前一序号节点 for(int i=0; i<n; i++) //初始化dist数组和path数组 { dist[i]=Edge[v0][i]; mon[i]=cost[v0][i]; // if(i!=v0&&dist[i]<Max) // path[i]=v0; // else path[i]=-1; } memset(s,0,sizeof(s)); //清零 s[v0]=1; dist[v0]=0; mon[v0]=0; for(int i=1; i<n; i++) { int Min=Max; int k=v0; for(int j=0; j<n; j++) //选择当前集合中最短路径的顶点k if(!s[j]&&dist[j]<Min) { Min=dist[j]; k=j; } s[k]=1; for(int j=0; j<n; j++) if(!s[j]&&Edge[k][j]<Max) { if(dist[k]+Edge[k][j]<dist[j]) { dist[j]=dist[k]+Edge[k][j]; mon[j]=mon[j]+cost[k][j]; // path[j]=k; } else if(dist[k]+Edge[k][j]==dist[j]&&mon[k]+cost[k][j]<mon[j]) { mon[j]=mon[j]+cost[k][j]; } } } cout<<dist[vn]<< " "<<mon[vn]<<endl; } int main() { int t; cin>>t; while(t--) { int n,m,s,d; cin>>n>>m>>s>>d; for(int i=0; i<n; i++) //初始化邻接矩阵 for(int j=0; j<n; j++) if(i==j) Edge[i][j]=0; else Edge[i][j]=Max; for(int i=0; i<m; i++) { int a,b,l,c; cin>>a>>b>>l>>c; Edge[a][b]=Edge[b][a]=l; cost[a][b]=cost[b][a]=c; } Dijkstra(n,s,d); } return 0; }
Bellman-Ford算法的流程如下： 给定图G(V, E)（其中V、E分别为图G的顶点集与边集），源点s，数组Distant[i]记录从源点s到顶点i的路径长度，初始化数组Distant[n]为, Distant[s]为0；
以下操作循环执行至多n-1次，n为顶点数： 对于每一条边e(u, v)，如果Distant[u] + w(u, v) < Distant[v]，则另Distant[v] = Distant[u]+w(u, v)。w(u, v)为边e(u,v)的权值； 若上述操作没有对Distant进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；
为了检测图中是否存在负环路，即权值之和小于0的环路。对于每一条边e(u, v)，如果存在Distant[u] + w(u, v) < Distant[v]的边，则图中存在负环路，即是说改图无法求出单源最短路径。否则数组Distant[n]中记录的就是源点s到各顶点的最短路径长度。
可知，Bellman-Ford算法寻找单源最短路径的时间复杂度为O(V*E).
Bellman－Ford算法可以大致分为三个部分 第一，初始化所有点。每一个点保存一个值，表示从原点到达这个点的距离，将原点的值设为0，其它的点的值设为无穷大（表示不可达）。 第二，进行循环，循环下标为从1到n－1（n等于图中点的个数）。在循环内部，遍历所有的边，进行松弛计算。 第三，遍历途中所有的边（edge（u，v）），判断是否存在这样情况： d（v） > d (u) + w(u,v)。
因为时间复杂多较高，可以参照：图结构练习——最短路径 的SPFA算法
