內(nèi)容：給定兩個頂點滓彰，在以這兩個點為起點和終點的路徑中，邊的權(quán)值和最小的路徑迂烁。如果把權(quán)值當(dāng)作距離看尼，考慮最短距離的話就很容易理解了。
最短路的例子
單源最短路問題1（Bellman-Ford算法）
單源最短路問題是固定一個起點盟步，求它到其他所有點的最短路的問題藏斩。終點也固定的問題叫做兩點之間最短路問題。但是因為解決單源最短路問題的復(fù)雜度也是一樣的却盘，因此通常當(dāng)作單源最短路問題來求解
記從起點s出發(fā)到頂點i的最短距離為d[i]狰域，則下述等式成立。
d[i]=min{d[j]+(從j到i的邊的權(quán)值)|e=(j,i)∈E}
如果給定的圖是一個DAG（有向無環(huán)圖）就可以按拓撲序給定點編號黄橘，并利用用這條遞推關(guān)系式計算出d北专。但是，如果圖中有圈旬陡，就無法以來這樣的順序進行計算。在這種情況下语婴，記當(dāng)前到頂點i的最短路長度為d[i]描孟，并設(shè)初值d[s]=0,d[i]=INF(足夠大的常數(shù))，再不斷使用這條遞推關(guān)系式更新d的值砰左，就可以算出新的d匿醒。只要圖中不存在負圈，這樣的更新操作就是有限的缠导。結(jié)束之后的d就是所求的最短距離了廉羔。
模板
//從頂點from指向頂點to的權(quán)值為cost的邊
struct edge{
int from,to,cost;
};
edge es[MAX_E];//邊
int d[MAX_V];//最短距離
int V,E;//V是頂點數(shù)，E是變數(shù)
//求解從頂點s出發(fā)到所有點的最短距離
void shortest_path(int s){
for(int i=0;i<V;i++)
d[i]=INF;
d[s]=0;
while(true){
bool updata=false;
for(int i=0;i<E;i++){
edge e=es[i];
if(d[e.from]!=INF&&d[e.to]>d[e.from]+e.cost){
d[e.to]=d[e.from]+e.cost;
update=true;
}
}
if(!update)
break;
}
}
這個算法叫做Bellman-Ford算法僻造。如果在圖中不存在從s可達的負圈憋他，那么最短路不會經(jīng)過同一個頂點兩次（也就是說孩饼，最多通過|V|-1條邊），while（true）的循環(huán)也最多執(zhí)行|V|-1次竹挡，因此镀娶，復(fù)雜度是O（|V|*|E|）。反之揪罕，如果存在從s可達的負圈梯码，那么在第|V|次循環(huán)中也會更新d的值，因此也可以用這個性質(zhì)來檢查負圈好啰。如果一開始對所有的頂點i轩娶，都把d[i]初始化為0，那么可以檢查出所有的負圈框往。
//如果返回true則存在負圈
bool find_negative_loop(){
memset(d,0,sizeof(d));
for(int i=0;i<V;i++){
for(int j=0;j<E;j++){
edge e=es[j];
if(d[e.to]>d[e.from]+e.cost){
d[e.to]=d[e.from]+e.cost;
//如果第n次仍然更新了鳄抒，則存在負圈
if(i==V-1)
return true;
}
}
}
return false;
}
?
單源最短路問題2（Dijkstra算法）//迪杰克斯拉
讓我們考慮沒有負邊的情況。在Bellman-Ford算法中搅窿，如果d[i]還不是最短距離的話嘁酿，那么即使進行d[j]=d[i]+(從i到j(luò)的邊的權(quán)值的更新)，d[j]也不會變成最短距離男应。而且?d[i]沒有變化闹司，每一次循環(huán)也要檢查一遍從i出發(fā)的所有邊。這顯然是很浪費時間的沐飘。因此可以對算法做如下修改游桩。
- 找到最短距離和已經(jīng)確定的頂點，從它出發(fā)更新相鄰頂點的最短距離耐朴。
-
此后不需要再關(guān)心1中的“最短距離已經(jīng)確定的頂點”
上面提到的“最短距離已經(jīng)確定的頂點”要怎么得到是問題的關(guān)鍵借卧。在最開始時，只有起點和最短距離是確定的筛峭。而在尚未使用過的頂點中铐刘，距離d[i]最小的頂點就是最短距離已經(jīng)確定的頂點。這是因為由于不存在負邊影晓，所以d[i]不會在之后的更新中變小镰吵。這個算法叫做Dijkstra算法。
int cost[MAX_V][MAX_V];//cost[u][v]表示邊e=（u挂签，v）的權(quán)值（不存在邊是設(shè)為INF）
int d[MAX_V];//頂點s出發(fā)的最短距離
bool used[MAX_V];//已經(jīng)使用過的圖
int V;//頂點數(shù)
//求從起點s出發(fā)到各個頂點的最短距離
void dijkstra(int s){
fill(d,d+V,INF);
fill(used,used+V,false);
d[s]=0;
while(true){
int v=-1;
//從尚未使用過的頂點中選擇一個距離最小的頂點
for(int u=0;u<V;u++){
if(!used[u]&&(v==-1||d[u]<d[v]))
v=u;
}
if(v==-1)
break;
used[v]=true;
for(int u=0;u<V;u++){
d[u]=min(d[u],d[v]+cost[v][u]);
}
}
}
使用鄰接矩陣實現(xiàn)的Dijkstra算法的復(fù)雜度是O(|V|2)疤祭。使用鄰接表的話，更新最短距離只需要訪問每一條邊即可饵婆，因此最終復(fù)雜度還是O(|V|2)勺馆。在|E|比較小時，大部分的時間花在了查找下一個使用的頂點上，因此需要使用合適的數(shù)據(jù)結(jié)構(gòu)對其進行優(yōu)化草穆。
需要優(yōu)化的是數(shù)值插入（更新）和取出最小值的兩個操作灌灾，因此使用堆就可以了。把每個頂點當(dāng)前的最短距離用堆維護续挟，在更新最短距離時紧卒，把對應(yīng)的元素往根的方向移動以滿足堆的性質(zhì)，而每次從堆中取出的最小值就是下一次要使用的頂點诗祸。這樣堆中元素共有O（|V|）個跑芳，更新和取出數(shù)值的操作有O（|E|）次，因此整個算法的復(fù)雜度是O（|E|log|V|）
下面是使用STL的priority_queue實現(xiàn)直颅。在每次更新時網(wǎng)堆里插入當(dāng)前最短距離和頂點的值對博个。插入的次數(shù)是O（|E|）次，因此元素也是O（|E|）個功偿。當(dāng)取出的最小值不是最短距離的話盆佣，就丟棄這個值。這樣整個算法也可以在同樣的復(fù)雜度內(nèi)完成械荷。
struct edge{
int to,cost;
};
typedef pair<int,int> P;//first是最短距離共耍，second是頂點的編號
int V;
vector<edge> G[MAX_V];
int d[MAX_V];
void dijkstra(int s){
//通過greater<P>參數(shù)，堆參照first從小到大的順序取出值
priority_queue<P,vector<P>,greater<P> > que;
fill(d,d+V,INF);
d[s]=0;
que.push(P(0,s));
while(!que.empty()){
P p=que.top();
que.pop();
int v=p.second;
id(d[v]<p.first)
continue;
for(int i=0;i<G[V].size();i++){
edge e=G[v][i];
if(d[e.to]>d[v]+e.cost){
d[e.to]=d[v]+e.cost;
que.push(P(d[e.to],e.to));
}
}
}
}
?
任意兩點間的最短路問題（Floyd-Warshall算法）
求解所有兩點間的最短路問題叫做任意兩點間的最短路問題吨瞎。讓我們試著用DP求解任意兩點間的最短路問題痹兜。只是用頂點
0 ~ k和i，j的情況下颤诀，記i到j(luò)的最短路長度為d[k+1][i][j]字旭，當(dāng)k=-1時，認為只使用i和j崖叫，所以d[0][i][j]=cost[i][j]遗淳。接下來讓我們把只使用頂點0k的問題歸約到只使用0k-1 的問題上。
只使用0~k時心傀，我們分i到j(luò)的最短路正好經(jīng)過頂點k一次和完全不經(jīng)過頂點k兩種情況來討論屈暗。不經(jīng)過頂點k的情況下，d[k][i][j]=d[k-1][i][j]脂男。通過頂點k的情況下养叛，d[k][i][j]=d[k-1][i][k]+d[k-1][k][j]。合起來就得到了d[k][i][j]=min(d[k-1][i][j],d[k-1][i][k]+d[k-1][k][j])這個DP也可以使用同一個數(shù)組疆液，不斷進行d[i][j]=min(d[i][j],d[i][k]+d[k][j])的更新來實現(xiàn)。
這個算法叫做Floyed-Warshall算法陕贮，可以在O（|V^3|）時間里求得所有兩點間的最短路長度堕油。Floyd-Warshall算法和Bellman-Ford算法一樣，可以處理邊時負數(shù)的情況。而判斷圖中是否有負圈掉缺，只需要檢查是否存在d[i][i]是負數(shù)的頂點i就可以了卜录。
int d[MAX_V][MAX_V];//d[u][v]表示邊e=(u,v)的權(quán)值（不存在時設(shè)為INF,不過d[i][i]=0）
int V;//頂點數(shù)
void warshall_floyd(){
for(int k=0;k<V;k++)
for(int i=0;i<V;i++)
for(int j=0;j<V;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
這樣通過三重循環(huán)非常簡單地就可以求出所有兩點間的最短路長度。由于實現(xiàn)起來非常簡單眶明，如果復(fù)雜度在可以承受的范圍之內(nèi)艰毒，單源最短路也可以使用Floy-Warshall算法進行求解
?
路徑還原
截至目前，我們都只是在求解最短距離搜囱。雖然許多問題只需輸出最短距離就可以了丑瞧，但是也有問題需要求解最短路的路徑。我們以Dijkstra算法為例蜀肘，試著來求解最短路徑绊汹。在求解最短距離時，滿足d[j]=d[k]+cost[k][j]的頂點k扮宠，就是在最短路上頂點j的前趨節(jié)點西乖，因此通過不斷尋找前趨節(jié)點就可以恢復(fù)出最短路，時間復(fù)雜度時O(|E|)坛增。
此外获雕，如果用prev[j]來記錄最短路上頂點j的前趨，那么就可以在O（|V|）的時間內(nèi)完成最短路的回復(fù)收捣，在d[j]被d[j]=d[k]+cost[k][j]更新時届案，修改prev[j]=k;這樣就可以求得prev數(shù)組。在計算從s出發(fā)到j(luò)的最短路時坏晦，通過prev[j]就可以知道頂點j的前趨萝玷，因此不斷把j替換成prev[j]直到j(luò)=s為止就可以了。Bellman-Ford算法和Floyd-Warshall算法都可以用類似的方法進行最短路的還原昆婿。
int prev[MAX_V];//最短路上的前趨頂點
//求從起點s出發(fā)到各個頂點的最短距離
void dijkstra(int s){
fill(d,d+V,INF);
fill(used,used+V,false);
fill(prev,prev+V,-1);
d[s]=0;
while(true){
int v=-1;
for(int u=0;u<V;u++){
if(!used[u]&&(v==-1||d[u]<d[v]))
v=u;
}
if(v==-1)
break;
used[v]=true;
for(int u=0;u<V;u++){
if(d[u]>d[v]+cost[v][u]){
d[u]=d[v]+cost[v][u];
prev[u]=v;
}
}
}
}
//到頂點t的最短路
vector<int> get_path(int t){
vector<int> path;
for(;t!=-1;t=prev[t])
path.push_back(t);//不斷沿著prev[t]走直到t=s
//這樣得到的就是按照t到s的順序球碉，所以需要翻轉(zhuǎn)
reverse(path.begin(),path.end());
return path;
}
?
Emergency
練手題
hhh這道題笑shi我了，明明PAT AC的分數(shù)是25分仓蛆，我還以為我的代碼只有25分//傻了
這道題涉及的不僅僅是每條路徑的值睁冬，還有每座城市都有一個權(quán)值（點權(quán)），還有相關(guān)的最短路的路徑有多少條看疙，將c1到每個城市的相同的路徑計算有多少條豆拨。
#include <iostream>
#include <cstdio>
using namespace std;
const int inf=99999999;
int n,m,c1,c2;
int e[510][510],weight[510],dis[510],num[510],w[510];
bool visit[510];
void dijkstra(){
fill(visit,visit+510,false);
fill(dis,dis+510,inf);
dis[c1]=0;
w[c1]=weight[c1];
num[c1]=1;
while(true){
int v=-1;
int minn=inf;
for(int u=0;u<n;u++){
if(!visit[u]&&dis[u]<minn){
v=u;
minn=dis[u];
}
}
if(v==-1)
break;
visit[v]=true;
for(int u=0;u<n;u++){
if(!visit[u]&&e[v][u]!=inf){
if(dis[v]+e[v][u]<dis[u]){
dis[u]=dis[v]+e[v][u];
num[u]=num[v];
w[u]=w[v]+weight[u];
}else if(dis[v]+e[v][u]==dis[u]){
num[u]=num[v]+num[u];
if(w[v]+weight[u]>w[u])
w[u]=w[v]+weight[u];
}
}
}
}
printf("%d %d",num[c2],w[c2]);
}
int main()
{
//freopen("data","r",stdin);
scanf("%d%d%d%d",&n,&m,&c1,&c2);
for(int i=0;i<n;i++)
cin>>weight[i];
fill(e[0],e[0]+510*510,inf);
int a,b,c;
for(int i=0;i<m;i++){
cin>>a>>b>>c;
e[a][b]=e[b][a]=c;
}
dijkstra();
return 0;
}
?
Travel Plan
路徑還原
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, s, D;
int e[501][501],cost[501][501],d[501],c[501];
bool visit[501];
const int inf=99999999;
int pre[501];
void dijkstra(){
fill(d,d+501,inf);//記錄e
fill(c,c+501,inf);//記錄cost
fill(visit,visit+501,false);
d[s]=0;
c[s]=0;
while(true){
int v=-1;
int minn=inf;
for(int u=0;u<n;u++){
if(!visit[u]&&d[u]<minn){
minn=d[u];
v=u;
}
}
if(v==-1)
break;
visit[v]=true;
for(int u=0;u<n;u++){
if(!visit[u]&&e[v][u]!=inf){
if(d[v]+e[v][u]<d[u]){
d[u]=d[v]+e[v][u];
c[u]=c[v]+cost[v][u];
pre[u]=v;
}else if(d[u]==d[v]+e[v][u]&&c[u]>c[v]+cost[v][u]){
c[u]=c[v]+cost[v][u];
pre[u]=v;
}
}
}
}
}
void dfs(int u){
if(u==s)
return;
dfs(pre[u]);
cout<<u<<" ";
}
int main(){
// freopen("data","r",stdin);
cin>>n>>m>>s>>D;
fill(e[0],e[0]+501*501,inf);
fill(cost[0],cost[0]+501,inf);
int a,b,w,g;
for(int i=0;i<m;i++){
cin>>a>>b>>w>>g;
e[a][b]=e[b][a]=w;
cost[a][b]=cost[b][a]=g;
}
dijkstra();
cout<<s<<" ";
dfs(D);
cout<<d[D]<<" "<<c[D]<<endl;
return 0;
}
?
All Roads Lead to Rome
多條件
#include<stdio.h>
#include<map>
#include<string>
#include<string.h>
#include<stack>
using namespace std;
#define MAX 210
int INF = 1000000;
int happy[210];
int visit[MAX];
int e[MAX][MAX];
int d[MAX];
int h[MAX];
int num[MAX];
int pre[MAX];
int count[MAX],n;
void dijkstra(int begin)
{
d[begin] = 0;
h[begin] = happy[begin];
num[begin] = 1;
count[begin] = 0;
while(true)
{
int v = -1;
int minn = INF;
for(int u = 0 ;u <n ;u++)
{
if(!visit[u] && d[u] < minn)
{
v = u;
minn= d[u];
}
}
if(v == -1) return ;
visit[v] = true;
for(int u = 0 ;u <n ;u++)
{
if(!visit[u] && e[v][u]!=INF)
{
if(d[v]+e[v][u]<d[u])
{
d[u] = d[v]+e[v][u];
num[u] = num[v];
h[u] = h[v] + happy[u];
pre[u] = v;
count[u] = count[v] +1;
}
else if(d[v]+e[v][u]==d[u])
{
num[u] = num[u] + num[v];
if(h[u] < h[v] + happy[u])
{
h[u] = h[v] + happy[u];
count[u] = count[v] +1;
pre[u] = v;
}
else if( h[u] == h[v] + happy[u] && (double)(h[v] + happy[u])/(count[v]+1) > (double)h[u]/count[u])
{
count[u] = count[v] +1;
pre[u] = v;
}
}
}
}
}
}
int main()
{
int i,j,K,Happy,ROM;
char begin[4],tem[4];
scanf("%d%d%s",&n,&K,begin);
map<string,int> mm;
map<int,string> mm2;
mm[begin] = 0;
mm2[0] = begin ;
happy[mm[begin]] = 0;
for(i = 1 ; i < n ;i++)
{
scanf("%s%d",tem,&Happy);
if(strcmp("ROM",tem)==0) ROM = i;//這里可以不要
mm[tem] = i;
mm2[i] = tem;
happy[i] = Happy;
}
char x[4],y[4];
fill(e[0],e[0]+MAX*MAX,INF);
fill(d,d+MAX,INF);
fill(h,h+MAX,INF);
fill(pre,pre+MAX,-1);
fill(count,count+MAX,0);
for(i = 0 ; i < K ;i++)
{
scanf("%s%s",x,y);
scanf("%d",&e[mm[x]][mm[y]]);
e[mm[y]][mm[x]] = e[mm[x]][mm[y]];
}
dijkstra( mm[begin]);
printf("%d %d %d %d\n",num[mm["ROM"]],d[mm["ROM"]],h[mm["ROM"]],h[mm["ROM"]]/count[mm["ROM"]]);
stack<int> ss;
i= mm["ROM"];
while(i != -1)
{
ss.push(i);
i = pre[i];
}
int fir = 1;
while(!ss.empty())
{
if(fir == 1)
{
fir = 0;
printf("%s",mm2[ss.top()].c_str());
}
else printf("->%s",mm2[ss.top()].c_str());
ss.pop();
}
printf("\n");
return 0;
}
?
HDU Today
STL map+Dijkstra
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define MAX 2100
int INF = 99999999,n;
int e[MAX][MAX],d[MAX];
bool visit[MAX];
map <string,int>mm;
string a,b,s,aend;
int c,k=1;
void dijkstra(){
fill(d,d+k+1,INF);
fill(visit,visit+k,false);
d[1]=0;
while(true){
int v=-1;
for(int u=1;u<=k;u++){//這里千萬不能是n
if(!visit[u]&&(v==-1||d[u]<d[v])){
v=u;
}
}
if(v==-1){
break;
}
visit[v]=true;
for(int u=1;u<=k;u++){
if(!visit[u]&&e[v][u]!=INF){
if(d[u]>d[v]+e[v][u]){
d[u]=d[v]+e[v][u];
}
}
}
}
}
int main(){
while(cin>>n&&n!=-1){
mm.clear();
cin>>s>>aend;
//用map映射給站名標記，起始站為1能庆，終點站為2
//怪不得之前的代碼總是bug
k=1;//這里忘記初始化施禾，every time 卡了那么久，原來是在這里
mm[s]=k++;
mm[aend]=k++;
//初始化e
for(int i=0;i<155;i++){
for(int j=0;j<155;j++){
if(i==j)
e[i][j]=0;
else
e[i][j]=INF;
}
}
for(int i=1;i<=n;i++){
cin>>a>>b>>c;
if(!mm[a])
mm[a]=k++;
if(!mm[b])
mm[b]=k++;
if(c<e[mm[a]][mm[b]])
e[mm[a]][mm[b]]=e[mm[b]][mm[a]]=c;
}
if(s==aend)
cout<<"0"<<endl;
else{
dijkstra();
if(d[2]==INF)
cout<<"-1"<<endl;
else
cout<<d[2]<<endl;
}
}
return 0;
}
