临清网站建设价格,做网站优化有什么好处,福州做网站的公司,app推广赚钱平台最短路
单源最短路
所有边权都是正数
朴素Dijkstra算法
基本思路:从1号点到其他点的最短距离
步骤:
定义一个s集合包含当前已确定最短距离的点
1、初始化距离dis[1] 0,dis[其它] 正无穷
2、for i 0-n循环n次 2.1找到不在s中的距离最近的点 -t 2.2把t加到s当中去…最短路
单源最短路
所有边权都是正数
朴素Dijkstra算法
基本思路:从1号点到其他点的最短距离
步骤:
定义一个s集合包含当前已确定最短距离的点
1、初始化距离dis[1] 0,dis[其它] 正无穷
2、for i 0-n循环n次 2.1找到不在s中的距离最近的点 -t 2.2把t加到s当中去 2.3用t来更新其它点的距离
模板代码如下:
#includeiostream
#includecstring
#includealgorithmusing namespace std;const int N 510;
int n,m;
int g[N][N];
//dis表示从1号点到其它点的距离
int dist[N];
//st表示每个点的最短路是否确定
bool st[N];int dijkstra()
{memset(dist,0x3f,sizeof dist);dist[1] 0;for(int i 0;i n; i ){int t -1;for(int j 1;j n;j )if(!st[j] (t -1 || dist[t] dist[j]))t j;st[t] true;for(int j 1;j n;j )dist[j] min(dist[j],dist[t] g[i][j]);}if(dist[n] 0x3f3f3f3f) return -1;return dist[n];
}
int main()
{scanf(%d%d, n, m);//初始化memset(g,0x3f,sizeof g);int t dijkstra();printf(%d\n,t);return 0;
}堆优化版的Dijkstra算法
#includeiostream
#includecstring
#includealgorithm
#includequequeusing namespace std;const int N 100010;
int n,m;
//存储方式改为邻接表的形式
int h[N],w[N],e[N],ne[N],idx;
//dis表示从1号点到其它点的距离
int dist[N];
//st表示每个点的最短路是否确定
bool st[N];void add(int a,int b,int c)
{e[idx] b,w[idx] c,ne[idx] h[a],h[a] idx ;
}int dijkstra()
{memset(dist,0x3f,sizeof dist);dist[1] 0;priority_queuePII,vectorPII,greaterPII heap;heap.push({0,1});while(heap.size --){auto t heap.top();heap.pop();int ver t.second,distance t.first();if (st[ver]) continue;for(int i h[ver];i ! -1;i ne[i]){int j e[i];if(dist[j] distance w[i]){dist[j] distance w[i];heap.push({dist[j],j});}}}if(dist[n] 0x3f3f3f3f) return -1;return dist[n];
}
int main()
{scanf(%d%d, n, m);//初始化memset(h,-1,sizeof h);while(m --){int a,b,c;scanf(%d%d%d,a,b,c);add(a,b,c);}int t dijkstra();printf(%d\n,t);return 0;
}存在负权边
Bellman-Ford算法
基本思路:n次迭代每次循环所有边每次循环更新最短距离
#includeiostream
#includecstring
#includealgorithmusing namespace std;const int M 100010, N 510;int n,m,k;
int dist[N],backup[N];struct Edge
{int a,b,w;}edges[M];int bellman_ford()
{memset(dist,0x3f,sizeof dist);dist[1] 0;for(int i 0;i k;i ){//保存上一次的结果memcpy(backup,dist,sizeof dist);for(int j 0;j m;j ){int a edges[j].a,b edges[j].b,w edges[j].w;dist[b] min(dist[b],backup[a] w);}}if(dist[n] 0x3f3f3f3f / 2) return -1;return dist[n];
}int main()
{scanf(%d%d%d,n,m,k);for(int i 0;i m;i ){int a,b,w;scanf(%d%d%d,a,b,w);edges[i] {a,b,w};}int t bellman_ford();if(t -1){puts(impossible);}else printf(%d\n,t);return 0;
}SPFA算法
对Bellman-Ford算法的一个优化
#includeiostream
#includecstring
#includealgorithm
#includequequeusing namespace std;const int N 100010;
int n,m;
//存储方式改为邻接表的形式
int h[N],w[N],e[N],ne[N],idx;
//dis表示从1号点到其它点的距离
int dist[N];
//st表示每个点的最短路是否确定
bool st[N];void add(int a,int b,int c)
{e[idx] b,w[idx] c,ne[idx] h[a],h[a] idx ;
}int spfa()
{memset(dist,0x3f,sizeof dist);queueint q;q.push(1);st[1] true;while(q.size()){int t q.front();q.pop();st[t] false;for(int i h[t];i ! -1;i ne[i]){int j e[i];if(dist[j] dist[t] w[i]){dist[j] dist[t] w[i];if(!st[j]){q.push(j);st[j] true;}}}}if(dist[n] 0x3f3f3f3f) return -1;return dist[n];}
int main()
{scanf(%d%d, n, m);//初始化memset(h,-1,sizeof h);while(m --){int a,b,c;scanf(%d%d%d,a,b,c);add(a,b,c);}int t spfa();if(t -1) puts(false);else printf(%d\n,t);return 0;
}多源汇最短路
Floyd
利用临界矩阵来存储
#includeiostream
#includecstring
#includealgorithmusing namespace std;const int N 210,INF 1e9;int n,m,Q;
int d[N][N];void floyd()
{for(int k 1;k n;k )for(int i 1;i n;i )for(int j 1;j n;j )d[i][j] min(d[i][j],d[i][k] d[k][j]);
}
int main()
{scanf(%d%d%d,n,m,Q);for(int i 1;i n;i ){for(int j 1;j n;j )if(i j) d[i][j] 0;else d[i][j] INF;}while(m --){int a,b,w;scanf(%d%d%d,a,b,w);d[a][b] min(d[a][b],w);}floyd();while(Q --){int a,b;scanf(%d%d,a,b);if(d[a][b] INF / 2) puts(impossible);printf(%d\n,d[a][b]);}return 0;
}
