ps：本来是复习图论的，最后变成了预习，隔了一段时间简直了，重新学过！
哈哈哈哈哈哈哈，，真的菜啊！
单源最短路问题是求，，固定一个起点，求它到其他所有点的最短路问题。
两点之间最短路是求，固定起点和终点求最短路
两者没有根本区别，复杂度也是一样的
1，单源最短路1 bellman-ford算法
核心算法：
d[i]=min(d[j]+(从顶点j到顶点i边的权值)，d[i]）
d【i】表示任意点到顶点i的最短距离
一般初始化为INF，，然后起点d【s】初始化0。
只要图中不存在负圈（负圈是指两点间权值为负数所形成的圈）更新操作就是有限的
struct edge// 从顶点from——>to的权值为cost的边{ int from; int to; int cost;};edge es[maxn]; //边int d[maxn]; //最短距离int v,b; //分别为顶点和边数void bellman(int s)//从顶点开始递归{ for(int i=0;i d[e.from]+e.cost) { d[e.to]=d[e.from]+e.cost; update=true; } } if(!update)break; } } 算了找到了大佬的详细思路，我看懂了再来补把
bellman-ford算法：http://www.wutianqi.com/?p=1912
附上自己盲敲的代码，和大佬的一样
#include#include #include #include #include #include #include #include
dijkstra算法：
查错查了两个小时啊，我tm开心。
// 普通版迪杰斯特拉 o（n*n）
//#include<iostream>
//#include<cstdio>//#include<cstring>//#include<cmath>//#include<queue>//#include<set>//#include<algorithm>//#include<map>//#define maxn 1000//#define inf 100000//using namespace std;//int n,bian;//int mp[maxn][maxn];//int u,v,cost;//int dis[maxn];//int pre[maxn];//void init()//{ // cin>>n>>bian;// //memset(mp,inf,sizeof(mp));// for(int i=1;i<=n;i++)// for(int j=1;j<=n;j++)// mp[i][j]=inf;// for(int i=0;i<bian;i++){ // cin>>u>>v>>cost;// mp[u][v]=cost;// mp[v][u]=cost;// }// for(int i=1;i<=n;i++)// { // dis[i]=inf;// }//}//void dijkstra(int n,int v)//{ // bool vis[maxn];// for(int i=1;i<=n;i++)// { // vis[i]=false;// dis[i]=mp[v][i];// if(dis[i]==inf)// { // pre[i]=0;// }// else pre[i]=v;// }// dis[v]=0;// vis[v]=true;// for(int i=2;i<=n;i++)// { // int u=v;// int mazz=inf;// for(int j=1;j<=n;j++){ // if(!vis[j]&&dis[j]<mazz)//换dis最小的顶点继续查找// { // u=j;// mazz=dis[j];// }// }// vis[u]=true;// for(int k=1;k<=n;k++)//更新顶点上的dis// { // if(!vis[k]&&mp[u][k]<inf)// { // if(dis[k]>mp[u][k]+dis[u]){ // dis[k]=mp[u][k]+dis[u];// pre[k]=u;// }// }// }//// }//}//void chazhaolujing(int *pre,int v,int n)//{ // int tot=1;// int que[maxn];// que[tot++]=n;// int tem=pre[n];// while(tem!=v)// { // que[tot]=tem;// tot++;// tem=pre[tem];// }// que[tot]=v;// for(int i=tot;i>=1;i--)// { // if(i!=1)cout<<que[i]<<"-->";// else cout<<que[i]<<endl;// }////}//int main()//{ // init();// dijkstra(n,1);// cout<<dis[n]<<endl;// chazhaolujing(pre,1,n);// return 0;//}
//5
//7//1 2 10//1 4 30//1 5 100//2 3 50//3 5 10//4 3 20//4 5 60//输出数据://60//1 -> 4 -> 3 -> 5 //优先队列优化版的迪杰斯特拉 0（n*logn）#include<iostream>
#include<cstdio>#include<cstring>#include<cmath>#include<queue>#include<set>#include<algorithm>#include<map>#define maxn 1000using namespace std;const int inf=1e9+7;vector<pair<int ,int> >e[maxn];//建立图int dis[maxn];void init(){ for(int i=0;i<maxn;i++) e[i].clear(); for(int i=0;i<maxn;i++) dis[i]=inf;}int n,m;void dijkstra(int s){ priority_queue<pair<int,int> >q; dis[s]=0; q.push(make_pair(-dis[s],s)); while(!q.empty()) { int now=q.top().second; q.pop(); for(int i=0;i<e[now].size();i++) { int v=e[now][i].first;//为了用起来方便而赋值 if(dis[v]>dis[now]+e[now][i].second)//更新顶点的dis值 { dis[v]=dis[now]+e[now][i].second; q.push(make_pair(-dis[v],v)); } } }}int main(){ while(cin>>n>>m) { int i,j; init(); for(i=0; i<m; i++) { int x,y,z; scanf("%d %d %d",&x,&y,&z); e[x].push_back(make_pair(y,z));//e[x].push_back(y); e[y].push_back(make_pair(x,z)); } int s,t; scanf("%d %d",&s,&t); dijkstra(s); if(dis[t]==inf)cout<<"-1"<<endl; else cout<<dis[t]<<endl; } return 0;}//Sample Input
//3 3 0 1 1 0 2 3 1 2 1 0 2 3 1 0 1 1 1 2// ////Sample Output//2 -1
floyd算法：