1. Dijkstra算法
這個算法和prime求最小生成樹特別像，都是找到最小邊，把點加進來，然后用新加的點更新其他沒有被加進來的點。
1.
#define N 1002
2.
#define MAX 99999
3.
int edges[N][N],d[N],n;
4.
5.
void dijkstra(int v)
6.
{
7.
int i,j;
8.
bool s[N]={false};
9.
for(i=1;i<=n;i++)
10.
d[i]=edges[v][i];
11.
d[v]=0;s[v]=true;
12.
for(i=1;i<n;i++)
13.
{
14.
int temp=MAX;
15.
int u=v;
16.
for(j=1;j<=n;j++)
17.
if((!s[j])&&(d[j]<temp))
18.
{
19.
u=j;
20.
temp=d[j];
21.
}
22.
s[u]=true;
23.
for(j=1;j<=n;j++)
24.
if((!s[j])&&(edges[u][j]<MAX)&&(d[u]+edges[u][j])<d[j])
25.
d[j]=d[u]+edges[u][j];
26.
}
27.
28.
}
2. SPFA算法 （shortest path faster algorithm）
不斷維護一個隊列，如果隊列里的點，使得其他點的最短路得到松弛，則這個點還有可能使另外的點松弛，所以如果這個點不在隊列里，就把它入隊。
很多時候，給定的圖存在負權邊，這時類似Dijkstra等算法便沒有了用武之地，而Bellman-Ford算法的復雜度又過高，SPFA算法便派上用場了。 此算法時間復雜度為O（2*E），E為邊數。
//pku1860
#include<stdio.h>
#include<string.h>
#include<vector>
#define N 120
using namespace std;
struct Point
{
int id;
double r, c;
};
vector<Point> p[N];
int q[N],n,m,S,visit[N];
double V,dist[N];
int spfa()
{
memset(visit, 0, sizeof(visit));
int i,j,head=0,tail=1,x;
for(i=1; i<=n ;i++)
dist[i]=0; //此題是求換得的貨幣最多，所以初值賦0；
//若求最短路，初值應賦為無窮大
if(V<=0) return 0;
q[0]=S;
dist[S]=V; //S為源，若求最短路，則dist[S]=0;
visit[S]=1;
while(head!=tail){ // Attention！！！由于對隊列長度取模了，所以head<tail不一定成立，應改為head!=tail
x=q[head];
visit[x]=0;
head=(head+1)%N;
for(i=0; i<p[x].size(); i++){
j=p[x][i].id;
if(dist[j]<(dist[x]-p[x][i].c)*p[x][i].r){
dist[j]=(dist[x]-p[x][i].c)*p[x][i].r;
if(!visit[j]){
q[tail]=j;
tail=(tail+1)%N;
visit[j]=1; //若如果j點的最短路徑估計值有所調整，
// 且j點不在當前的隊列中，就將j點放入隊尾
}
}
}
if(dist[S]>V) return 1;
}
return 0;
}
int main()
{
int i,j,a,b;
double rab, cab, rba, cba;
Point p1, p2;
while(scanf("%d %d %d %lf",&n, &m, &S, &V)!=EOF){
for(i=1; i<=n; i++)
p[i].clear();
for(i=0; i<m; i++){
scanf("%d %d %lf %lf %lf %lf",&a, &b, &rab, &cab, &rba, &cba);
p1.id=b; p1.r=rab; p1.c=cab;
p2.id=a; p2.r=rba; p2.c=cba;
p[a].push_back(p1);
p[b].push_back(p2);
}
j=spfa();
if(j)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}