最短路算法、应用、模板总结

1.1.1 Floyd算法

1 d[x][y]->inf;
2 
3 for(int k=0;k<n;k++)//每两点间的最短路
4 
5     for(int i=0;i<n;i++)
6 
7         for(int j=0;j<n;j++)
8 
9              if (d[i][j]>d[i][k]+d[k][j]) d[i][j]=d[i][k]+d[k][j];

View Code

算法证明：n-1次松弛操作后必然得到最短路；

适用范围：1、稠密图效果更好；2、边权可正可负；

3、可判两点间是否有通路：第四行改成：d[i][j]=d[i][j]||(d[i][k]&&d[k][j])即可

有连通d[i][j]=true;称为有向图的传递闭包

1.1.2 Dijkstra算法(邻接矩阵)

条件：正权值，最短路一定可行，最长路在有正环的时候不能找到

 1 /*设源点是s*/
 2 
 3 /*初始化d[i][j]->max 注意是否有平行边、反向边*/
 4 
 5 bool vis[maxn];
 6 
 7 int d[maxn];
 8 
 9 memset(vis,0,sizeof(vis));
10 
11 for(int i=1;i<=n;i++)
12 
13 if (i==s) d[i]=0;else d[i]=INF;
14 
15 for(int i=1;i<=n;i++)
16 
17 {
18 
19 int max=INF,x;
20 
21 for(int j=1;j<=n;j++)
22 
23 if (!v[j] && d[j]<=max) max=d[x=j];
24 
25 vis[x]=true;
26 
27 for(int j=1;j<=n;j++)//松弛操作
28 
29 if(d[j]<d[x]+w[x][j]) d[j]=d[x]+w[x][j];
30 
31 }

View Code

/*****************************************************************************/

功能拓展：//最短路径,最小花费(最大花费也可做，但是不能有正环)

d->INF,cost->INF

d[s]=cost[s]=0;//最短路径,最小花费

Rec(i,1->n)

{

Rec(j,1->n)找到未标记中的最短路，最短路相同时找花费最小

标记点

Rec(j,1->n)//松弛操作先松弛最短路，最短路相同时松弛更小花费

}

/*****************************************************************************/

1.1.3 FIFO优化的Bell_man算法(邻接表、spfa)

 1 #define rec(i,n) for(int i=1;i<=n;i++)
 2 #define INF 0x3f3f3f3f
 3 const int maxn = 800 + 10 ;
 4 struct edge
 5 {
 6     int u,v,cap,pre;//cap表示花费
 7     edge(){}
 8     edge(int u,int v,int cap,int pre):
 9        u(u),v(v),cap(cap),pre(pre);
10 }edge[maxe];
11 int head[maxn],nedge;//表示读入的边的个数
12 void addedge(int u,int v,int cap)
13 {
14     edge[nedge]=edge(u,v,cap,head[u]);//将新的边加到队首
15     head[u]=nedge++;
16     /*edge[nedge]=edge(v,u,cap,head[v]);//将新的边加到队首
17     head[v]=nedge++;*///无向图时就要将这个加上
18 }
19 void edgeinit()//添边之前要初始化
20 {
21     nedge=0;
22     memset(head,-1,sizeof(head));
23 }
24 struct Dijkstra
25 {
26     int st,ed,n;
27     bool vis[maxn];
28     int d[maxn];
29     Dijkstra(){}
30     Dijkstra()(int st,int ed,int n):
31         st(st),ed(ed),n(n){init();}//新建时就会初始化    
32 
33     void init()
34     {
35         memset(vis,0,sizeof(vis));
36         rec(i,n)
37             if (i==st) d[i]=0;else d[i]=INF;
38     }
39     int solve()
40     {
41         queue<int>q;
42         while(!q.empty()) q.pop();
43         q.push(st);
44         while(!q.empty())
45         {
46             int x=q.front();//
47             q.pop();
48             if (vis[x]) continue;
49             vis[x]=true;
50             for(int e=head[x];e!=-1;e=edge[e].pre)
51             {
52                 int u=x,v=edge[e].v,w=edge[e].cap;
53                 if (d[u]+w<d[v])
54                 {
55                     d[v]=w+d[u];
56                     q.push(v);
57                 }
58             }
59         }
60     }
61     return d[ed];
62 }dijk;

View Code

/*操作方法：

edgeinit();

for(int i=1->e) addedge(u,v,cap);//防止有向边，无视平行边

dijk=(Dijkstra){st,ed,n};

ans=dijk.solve();

/*dijkstra综述* 对于有多个起点求到一个终点的最短路，可设置一个超级源点/

1.1.4最短路算法的应用

一、求图的中心

描述：对于一个任意一个节点i（i∈V），其他所有节点到i点的最短距离中的最大距离记为Dist[i],Dist最小的点就是图的中心

实现算法：floyd算法+枚举dist[i]

关键:实际应用的判断

二、求图的P中心

描述：p=2、3、4........

以p=2时来举个例子：有n个节点表示n个同学住的位置，两点间位置用无向图表示，现在要盖两个学校，当然每个学生都会选择就近的学校去学习，现在问选哪两个点i、j来盖学校，使走的最长的路最短（不是加和）。设dist[i][j]=max(min(d[x][j],d[x][i])...)，即使dist最小。

实现算法:floyd算法+枚举i、j

关键：枚举部分复杂度由点数n和p的个数决定，随p呈指数增长，任然是疑难问题。

三、求图的中央点

算法：服务点设置问题

Floyd最短路+枚举点i

Ans=∑(d[x][i]*value[x]) （x∈V，x≠i)求最小的ans