http://www.cnblogs.com/luweiseu/archive/2012/07/14/2591533.html
http://www.cnblogs.com/Yan-C/p/3916281.html
單源最短路徑定義為，給定起始頂點s，找出從s到圖中其它各頂點的最短路徑。求解單源最短路徑的算法主要是Dijkstra算法和Bellman-Ford算法，其中Dijkstra算法主要解決所有邊的權為非負的單源最短路徑問題，而Bellman-Ford算法可以適用于更一般的問題，圖中邊的權值可以為負。
全源最短路徑定義為，找出連接圖中各對頂點的最短路徑。求解全源最短路徑的算法主要有Floyd算法和Johonson算法，其中Floyd算法可以檢測圖中的負環(huán)并可以解決不包括負環(huán)的圖中的全源最短路徑問題；Johonson算法同樣也是解決不包含負環(huán)的圖的全源最短路徑問題，但是其算法效率更高。
待補充：
使用C++ vector鄰接表的Dijkstra算法模板。
Bellman-Ford的優(yōu)化：SPFA算法-->蟲洞問題。
BFS求解最短路徑。
暫時先使用鄰接矩陣表示圖，用for循環(huán)進行尋找最小值操作。
優(yōu)化時可以考慮鄰接表和優(yōu)先隊列。
Dijkstra （貪心）
Dijkstra算法解決的是帶權重的有向圖上單源最短路徑問題，該算法要求所有邊的權重都為正值。
該算法可以用優(yōu)先隊列進行優(yōu)化。
（1）核心算法
以下實現(xiàn)的時間復雜度為O(|V|^2)
int G[203][203];//二維數(shù)組 圖的存儲
int n, s, t;//n 點的個數(shù) , s 起點 ,t 終點
void dijkstra()
{
bool vis[203];//相當于集合Q的功能， 標記該點是否訪問過
int dis[203];//保存最短路徑
int i, j, k;
for(i=0;i<n;i++) {//初始化
dis[i] = G[s][i];//s—>各個點的距離
//if(i!=s && G[s][i] != INF) pre[i] = s;
//else pre[i] = -1;
}
memset(vis,false,sizeof(vis));//初始化為假 表示未訪問過
dis[s] = 0;//s->s 距離為0
vis[s] = true;//s點訪問過了，標記為真
for(i=1;i<n;i++)//G.V-1次操作+上面對s的訪問 = G.V次操作
{
k = -1;
for(j=0;j<n;j++)//從尚未訪問過的點中選一個距離最小的點
if(!vis[j] && (k==-1||dis[k]>dis[j]))//未訪問過 && 是距離最小的
k = j;
if(k == -1)//若圖是不連通的則提前結束
break;//跳出循環(huán)
vis[k] = true;//將k點標記為訪問過了
for(j=0;j<n;j++)//松弛操作
if(!vis[j] && dis[j]>dis[k]+G[k][j]) {//該點為訪問過 && 可以進行松弛
dis[j] = dis[k]+G[k][j];//j點的距離 大于當前點的距離+w(k,j) 則松弛成功，進行更新
//pre[j] = k;
}
}
printf("%d\n",dis[t]==MAX?-1:dis[t]);//輸出結果
}
（2）判斷有環(huán)
似乎不能？
（3）輸出路徑
通過pre數(shù)組從target輸出路徑。
（4）Dijkstra優(yōu)化
//pair 的first 保存的為最短距離, second保存的為頂點編號
typedef pair<int, int >P;//對組 不知道請自行百度
struct node
{
int v, w;//v 為到達的點, w為權重
int next;//記錄下一個結構體的位置 ，就向鏈表的next功能是一樣的
};
node edge[2003];//存所有的邊，因為是無向圖，所以*2
int cnt;//結構體的下標
int n, s, t;//n 點數(shù),s 起點,t止點
int head[203];//和鏈表的頭指針數(shù)組是一樣的。只不過此處head[u]記錄的為最后加入 edge 的且與u相連的邊在 edge 中的位置，即下標
void add(int u, int v, int w)//加邊操作
{
edge[cnt].v = v;
edge[cnt].w = w;
edge[cnt].next = head[u];//獲得下一個結構體的位置
head[u] = cnt++;//記錄頭指針的下標
}
void dijkstra()
{
int dis[203];//最短路徑數(shù)組
int i, v;//v保存從隊列中取出的數(shù)的第二個數(shù) 也就是頂點的編號
priority_queue<P,vector<P>,greater<P> >que;//優(yōu)先隊列 從小到大
node e;//保存邊的信息，為了書寫方便
P p;//保存從隊列取出的數(shù)值
fill(dis,dis+n,MAX);//初始化，都為無窮大
dis[s] = 0;//s—>s 距離為0
que.push(P(0,s));//放入距離 為0 點為s
while(!que.empty()){
p = que.top();//取出隊列中最短距離最小的對組
que.pop();//刪除
v = p.second;//獲得最短距離最小的頂點編號
if(dis[v] < p.first)//若取出的不是最短距離
continue;//則進行下一次循環(huán)
for(i=head[v];i!=-1;i=edge[i].next)//對與此點相連的所有的點進行遍歷
{
e = edge[i];//為了書寫的方便。
if(dis[e.v]>dis[v]+e.w){//進行松弛
dis[e.v]=dis[v]+e.w;//松弛成功
que.push(P(dis[e.v],e.v));//講找到的松弛成功的距離 和頂點放入隊列
}
}
}
printf("%d\n",dis[t]==MAX?-1:dis[t]);//輸出結果
}
int main()
{
int m, u, v, w;
while(scanf("%d %d",&n,&m)==2){//獲取點數(shù) 邊數(shù)
cnt = 0;//結構體下標從0開始
memset(head,-1,sizeof(head));//初始化head[N]數(shù)組
while(m--){
scanf("%d %d %d",&u,&v,&w);//獲取u,v,w(u,v)
add(u,v,w);//加邊
add(v,u,w);//加邊
}
scanf("%d %d",&s,&t);//獲取起止點
dijkstra();
}
return 0;
}
Bellman-Ford
Bellman-Ford算法誕生于20世紀50年代，對于不包含負環(huán)的圖，該算法可以簡單有效地求解圖的單源最短路徑問題。算法的基本思路非常簡單：以任意順序考慮圖的邊，沿著各條邊進行松弛操作，重復操作|V|次(|V|表示圖中頂點的個數(shù))。
http://blog.csdn.net/xu3737284/article/details/8973615
（1）核心算法
代碼來自http://blog.csdn.net/hsqlsd/article/details/7826319
O(VE)
struct Edge
{
int s,e;
int cost;
};
Edge edge[MAX];
int map[505][505];
int n,m,w;
int dist[MAX];
int edge_num;
bool bellman_ford()
{
int s,e,w,i,j;
bool flag;
for(i=1;i<=n;i++)
dist[i] = INF;
dist[1]=0;
for(i=1;i<=n;i++) //頂點下標從1開始,進行dist數(shù)組更新操作
{
flag=false;
for (j=0;j<edge_num;j++)
{
s=edge[j].s;
e=edge[j].e;
w=edge[j].cost;
if(dist[e]>dist[s]+w) //松弛迭代過程
{
dist[e]=dist[s]+w;
flag=true;
}
}
if(!flag)
break;
}
}
（2）判斷有環(huán)
http://www.tuicool.com/articles/YJzyee
struct node
{
int u, v, w;//u 為起點，v為終點，w為u—>v的權值
};
node edge[5203];
int n, m;//n 點數(shù) m 邊數(shù)
bool bellman_ford()
{
int i, j;
bool flag;
int dis[503];//保存最短路徑
fill(dis,dis+n,MAX);//初始化
dis[1] = 0;//因為判斷是否有負環(huán)，對整個圖而言，So s = 1;
//一下部分為 2) 第2~4行的操作
for(i=1;i<n;i++)//共需進行|V|-1次
{
flag = false;//優(yōu)化 初始化為假
for(j=0;j<m;j++)//對每一條邊
{
// if u.d>v.d+w(u,v) , u.d = v.d+w(u,v);
if(dis[edge[j].u]>dis[edge[j].v]+edge[j].w){//進行松弛
dis[edge[j].u] = dis[edge[j].v]+edge[j].w;//松弛操作成功
flag = true;//松弛成功變?yōu)檎? }
}
if(!flag)//若每條邊沒有松弛
break;//跳出循環(huán)
}
// 一下部分為 3) 第5~8行的操作
for(i=0;i<m;i++)
if(dis[edge[i].u]>dis[edge[i].v]+edge[i].w)//進行|V|-1次操作后 有邊還能進行松弛 說明
return true;//存在負環(huán)
return false;//不存在負環(huán)
}
（3）輸出路徑
Floyd-warshall（DP）
http://www.cppblog.com/wing/archive/2011/03/10/141511.html
（1）核心算法：
初始化，map[i][i] = 0;不可達=INF;
時間復雜度O(|V|^3)
void floyd(){
int i,j,k;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
dist[i][j]=map[i][j];
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
if(dist[i][k] != INF && dist[i][k] != INF
&& dist[i][k]+dist[k][j]<dist[i][j])
dist[i][j]=dist[i][k]+dist[k][j];
}
}
（2）判斷是否有負環(huán)
對于floyd判斷負環(huán)是否存在只需檢查是否存在d[i][i]是負數(shù)的頂點i即可。
（3）輸出路徑
path[][]={} //初始化為0
//if內同時進行以下兩個操作
dist[i][j] = dist[i][k] + dist[k][j];
path[i][j] = k;
//輸出函數(shù)的用法
cout<<"start ";
output(start, end);
//輸出函數(shù)
void output(int i,int j){
if(i==j) return;
if(path[i][j]==0) cout<<j<<' ';
else{
output(i,path[i][j]);
output(path[i][j],j);
}
}
