一、dijkstra
dijkstra解决不了带有负权值的最短路问题，因为disjkstra源于贪心算法，它计算的是每个点的最优解，前面确定好的点就不会影响后面点的松弛。在一条到目的地的路径上，前面得出的解不会因为后面的松弛而改变。但是如果路线中有负权值，这时则起点到某点的最最优解会改变，这时前面的一些点已经松弛过来，很多值无法更新了，所有得出的解是错的。因此需要另一种写法，学会了再说。
1.Til the Cows Come Home（例题）
#include<iostream>
#include<cstdio>
#define MAX 1000+4
#define inf 99999999
using namespace std;
//用二维数组储存边，遍历时按点松弛所有两点之间，时间复杂度较大。
int map[MAX][MAX];
int t,n;
int dis[MAX];
int book[MAX];
int v;
void init()//初始化二维数组，i==j表示本身初始化为0,其他初始化为无穷大，表示无限远。
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j)
{
map[i][j]=0;
}
else
map[i][j]=inf;
}
}
}
void dijk()
{
for(int i=1;i<=n;i++)//dis用于存目前有起点到i点的最优解，book标记松弛过的点。
{
book[i]=0;
dis[i]=map[1][i];
}
for(int i=1;i<=n-1;i++)//遍历除起点外的所有点，它更新了dis上存的最优解。
{
int _min=inf;
for(int j=1;j<=n;j++)//找出所有未松弛过的点中，最优的一个点（这里是最近的一个点）
{
if(book[j]==0&&_min>dis[j])
{
_min=dis[j];
v=j;
}
}
/*for(int i=1;i<=n;i++)
{
cout<<dis[i]<<" ";
}cout<<endl;*/
book[v]=1; //标记v点并松弛v点
for(int k=1;k<=n;k++)//遍历为被松弛的点，更新这些点的最优解。
{
if(book[k]==0&&dis[k]>dis[v]+map[v][k])
{
dis[k]=dis[v]+map[v][k];
}
}
}
printf("%d\n",dis[n]);
}
int main()
{
while(scanf("%d%d",&t,&n)!=EOF)
{
init();
for(int i=0;i<t;i++)//建立边。二维数组的i,j分别表示两点，map[i][j]存入权值。
{
int t1,t2,t3;
scanf("%d%d%d",&t1,&t2,&t3);
if(t3<map[t1][t2])
{
map[t1][t2]=t3;
map[t2][t1]=t3;
}
}
dijk();
}
}
2.Frogger （例题）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define MAX 300
#define inf 99999999
using namespace std;
int n,v,c=0;
int book[MAX];
double dis[MAX];
struct node
{
double a,b;
}s[MAX];
void init()
{
for(int i=1;i<=n;i++)
{
book[i]=0;
dis[i]=inf;
}
}
double D(int i,int j)//计算两点之间的距离。
{
double d=sqrt((s[i].a-s[j].a)*(s[i].a-s[j].a)+(s[i].b-s[j].b)*(s[i].b-s[j].b));
return d;
}
void dijk()
{
for(int i=1;i<=n;i++)//记录起点到它所连接的点的距离，存入dis；
{
dis[i]=D(1,i);
}
//题目需要找出其中一条路径上两个石头之间的最大距离，所以松弛时，取到该点最优解（dis）和该点到下一点距离的大值————————因为它求的是一条路上的大值
//再取{到下一点的最优解，和上述的最大值}取小值——————因为要找出所有路径中最短的值，我们可以绕过那些大距离的路径，走小距离的路，不影响到达目的地
for(int i=1;i<=n-1;i++)
{
int _min=inf;
for(int j=1;j<=n;j++)//找出dis中的最小值
{
if(book[j]==0&&_min>dis[j])
{
_min=dis[j];
v=j;
}
}
/*for(int j=1;j<=n;j++)
{
printf("%.3lf ",dis[j]);
}cout<<endl;*/
book[v]=1; //标记v，松弛v；
for(int j=1;j<=n;j++)
{
if(book[j]==0) //在未松弛的点中。max(dis[v],dD(v,j));得出起点经v到j的最大距离。
//min(~~~);得出上述最大值与到j点最优解取最小值，可以理解为起点经v到j的解和不经v到j的解，取小值
{
dis[j]=min(dis[j],max(dis[v],D(v,j)));
}
}
}
printf("Scenario #%d\nFrog Distance = %.3lf\n\n",c,dis[2]);
}
int main()
{
while(scanf("%d",&n))
{
c++;
if(n==0)
break;
init();
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&s[i].a,&s[i].b);
}
dijk();
}
}
二、spfa（队列优化的bellman）
相对 dijkstra节省时间复杂度，时间复杂度低，比较常用，它利用了邻接链表来储存边。因为它在松弛的时候，用了队列，所以对于多重条件的题目，我们可以用优先队列来处理，对入队元素选取优值，松弛，节省时间，甚至某种情况下还必须这样做。
1.信道安全(例题)
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int N=11000;
const int M=55000*2;
int vis[N],cnt,head[N],n,m;
double d[N];
struct node
{
int v,next;
double p;
}e[M];
void init()
{
memset(head,-1,sizeof(head));
cnt=0;
}
void add(int u,int v,double p)
{
e[cnt].v=v;
e[cnt].p=p;
e[cnt].next=head[u];//head[u]是点u的上一条边。他延续了上一条u点的边，初始值为-1.记录u点上一条边的位置（类似于链表）。
head[u]=cnt++;//cnt变量随着存入边的增加，记录着这条边存在第i个node上。更新head[u].
cout<<head[u]<<endl;;
}
double spfa()
{
for(int i=0;i<=n;i++)//初始化d，vis数组，d记录权值，vis标记以松弛过的点。
{
d[i]=0;
vis[i]=0;
}
//运用类似广搜的方法，将储存点所连接的所有边入队，逐步遍历相关的边：
/*如： 1-->3,4,5. 3,4,5-->q
3->2 2->q
4->5 5->q
5->1 1->q
*/
queue<int> q;//将起点入队。
q.push(1);
vis[1];
d[1]=1;
while(!q.empty())
{
int u=q.front();//取队首元素，以队首元素为点，遍历它连接的所有边。
q.pop();
vis[u]=0;
for(int i=head[u];i+1;i=e[i].next)
//取u点的head，它指向u点连接边储存的位置，在从该位置上取e[i].next。
//next指向下一个边的点（这些边都是u点的连接边）.i==-1时，u的边取尽了。这时e[i].next==-1,是第一次存入u点边的时候
{
/*cout<<i<<" ";
cout<<e[i].next<<endl;*/
int v=e[i].v;
double p=e[i].p;
if(d[v]<d[u]*p/100)//更新d值，取大值。如果v点（下一点）没有松弛过，则把v点入队，并标记。
{
d[v]=d[u]*p/100;
if(!vis[v])
{
vis[v]=1;
q.push(v);
}
}
}
//cout<<endl;
}
return d[n];
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
init();
for(int i=0;i<m;i++)//建立边。
{
int u,v;
double p;
scanf("%d%d%lf",&u,&v,&p);
add(u,v,p);
add(v,u,p);
}
printf("%.6f\n",spfa()*100);
}
}