做网站淘宝条形码,在柬埔寨做网站开发,wordpress热门插件,外包是做什么的算法之最短路径算法
最短路径算法
概念#xff1a; 考查最短路径问题#xff0c;可能会输入一个赋权图(也就是边带有权的图)#xff0c;则一条路径的v1v2…vN的值就是对路径的边的权求和#xff0c;这叫做赋权路径长#xff0c;如果是无权路径长就是单纯的路径上的边数。…算法之最短路径算法
最短路径算法
概念 考查最短路径问题可能会输入一个赋权图(也就是边带有权的图)则一条路径的v1v2…vN的值就是对路径的边的权求和这叫做赋权路径长如果是无权路径长就是单纯的路径上的边数。 在赋权图可能会出现负值边的情况这样当我们去找最短路径时可能会产生负值圈毕竟一直走负值边可以将数值变得更短。
单源最短路径问题
给定一个赋权图G(V,E)和一个特定顶点s作为输入找出从s到G中每一个其他顶点的最短赋权路径。
无权最短路径
给定一个无权图G(V,E)和一个起始顶点s作为输入找出从s到G中每一个其他顶点的最短路径。
广度优先搜索算法(BFS)
概念
广度优先搜索算法(BFS)用于在无权图或者边权相同的图中寻找最短路径。该方法按层处理顶点首先从起始点出发进行发散找到与起始点邻接的顶点a,…并将s到这些顶点的路径距离更新然后将该点标记成已经访问的顶点并将该点的前一个顶点记录下来(被标记的顶点我们后面遇到就认为该点已经不需要再进行处理了)然后再从顶点a,…发散找到该顶点的邻接顶点然后重复操作直到所有顶点都被标记完就完成了搜索。具体代码实现是用一个队列在迭代开始时队列中只含有距离为迭代距离currdist的那些顶点然后执行操作时将距离currdist1的顶点的那些顶点添加到队列中只要当前距离为currdist顶点处理完就会处理距离为currdist1(也就是当前顶点发散的顶点)的顶点添加到队列中。在队列中其实可以将know域也就是标记去掉因为队列的形式已经说明执行过了就不会在执行因此相当于标记了。
代码
//图的邻接表的结点信息
struct listnode{int data;bool flag; //判断是否访问过int path; //存储上一个顶点int dist; //距离listnode* next;
};//图的信息
class graph{
private:listnode *an; //邻接表形式存储图int vnum; //图中结点数
};//s为起点an数组的邻接表表示图
void BFS(int s){queueintq;q.push(s);an[s].dist0;while (!q.empty()){int vq.front();q.pop();an[v].flag true;listnode* pan[v].next;while (p! nullptr){if(an[p-data].distINT_MAX){an[p-data].distan[v].dist1;an[p-data].pathv;q.push(p-data);}pp-next;}}}Dijkstra算法
概念
用于求解赋权图的最短路径(无负值边)Dijkstra算法是解决单源最短路径问题的一般方法并且该解法是贪心算法。Dijkstra只是BFS的升级版使他能够求赋权图的最短路径如果求无权图Dijkstra跟BFS的做法一样Dijkstra算法是分阶段的该算法认为每一个阶段都将该阶段当作最好的情况处理类似于BFS算法但是还是有不同的地方比起BFS多出了需要进行每个阶段出现最好情况就进行更新路径。具体做法是从图中选取起始点v然后找出邻接点并将当前起始点到邻接点v3,v4…的距离更新如果是赋权图就是dvCv,v3(就是顶点v到v3的权)如果是无权就是dv1并将v标记为已知。然后选取邻接点集中的一点再做为起始点然后重复操作将当前顶点的前一个顶点记录。当v到某个顶点的距离在当前阶段是最小的(最好情况)那么就进行更新如果不是就无需更新。具体来说当我们扩展一个新结点时我们会考虑它的所有未访问过的邻接结点并计算从起始结点经过当前结点到达邻接结点的路径长度。如果这个长度小于已知的最短路径长度或者邻接结点的路径长度尚未初始化我们就更新邻接结点的路径长度。这样做的目的是通过不断更新路径长度来找到起始结点到所有其他结点的最短路径。实现的时候可以使用优先队列来进行优化算法只将顶点和其最短路径值进入队列中当队列非空执行以下操作u等于队顶的节点w等于队顶节点的最短路径值遍历u的所有边如果能找到节点v最短路径值小于v的当前值更新v将v压入队列。结束没有用优先队列优化的Dijkstra算法的时间复杂度为O(N²)如果使用优先队列则时间复杂度为O(nlogn)可以不用考虑已知域;
Dijkstra跟BFS区别
处理顶点 在BFS算法中当一个顶点被扩展时它的所有未访问过的邻居顶点都被添加到队列中这样它们将按照遍历的顺序逐个被访问。在Dijkstra算法中当一个顶点被扩展时它的邻居顶点也被考虑但是Dijkstra算法会计算扩展的顶点与其邻居之间的边的权重并根据这个权重来更新到达邻居顶点的最短路径长度。这个更新过程使得Dijkstra算法能够处理带有非负权重的图。 选择下一个顶点 在BFS算法中下一个要被扩展的顶点是队列中的下一个顶点也就是按照队列的先进先出FIFO原则选择。在Dijkstra算法中下一个要被扩展的顶点是距离起始点路径长度最小的顶点也就是根据已知的最短路径长度来选择。这需要使用优先队列或者最小堆来高效地选择路径长度最小的顶点。
代码
//图的邻接表的结点信息
struct listnode{int data;int path; //存储上一个顶点int dist; //最短距离int weight; //数组索引顶点跟该顶点的边的权重listnode* next;
};//图的信息
class graph{
private:listnode *an; //邻接表形式存储图int vnum; //图中结点数
};//v是起始点
void Dijkstra(int v){an[v].dist0;queueintq;q.push(v);while (!q.empty()){int wq.front();q.pop();listnode* pan[w].next;while (p! nullptr){if(an[w].distp-weightan[p-data].dist){an[p-data].distan[w].distp-weight;an[p-data].pathw;q.push(p-data);}pp-next;}}}题目模板 有向边单源最短路径问题
#include bits/stdc.h
using namespace std;const int INF0x3f3f3f3f;const int N10;
int n;struct edge {int v, w;
};bool vis[N1];int dijkstra(int start, const vectorvectoredge graph) {int minroad[n1];memset(minroad,INF,sizeof minroad);minroad[start] 0;priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq;pq.push({0, start});while (!pq.empty()) {auto [d, u] pq.top();pq.pop();if(vis[u]) continue;vis[u]true;for (const auto edges : graph[u]) {int v edges.v;int w edges.w;if (minroad[u] w minroad[v]) {minroad[v] minroad[u] w;pq.push({minroad[v], v});}}}return minroad[n]!INF?minroad[n]:-1;
}int main() {int m, start;cin n m start;vectorvectoredge graph(n 1);for (int i 0; i m; i) {int u, v, w;cin u v w;graph[u].push_back({v, w});}coutdijkstra(start, graph)endl;system(pause);return 0;
}Floyd算法
概念
Floyd(弗洛伊德)算法是基于动态规划思想的算法也称插点法是全源最短路算法(全源就代表经过一次Floyd算法每个点到各个点的最短路径都能算出来)用于求任意一对顶点间的最短路径此时图中的边的权值可以出现负数但不能出现负环时间复杂度为O(n³)n为点个数
基本思想
对于从i到j的弧进行n次试探首先考虑i0j是否存在如果存在则比较ij和i0j的路径长度去最短者进行更新ij的最短路径然后再添加顶点1依次类推。
具体过程
当一个图里有n个城市求全源最短路径问题定义城市k为从当前图拿出来并重新插入图中的城市城市i城市j分别为当前源城市和目的城市。dist[i\][j]表示城市i到城市j的最短路径假设当前图中没有城市k我们将城市k重新插入到图中我们需要判断城市i到城市j的最短路径是否要更新则比较路径经过城市k和原来的路径长度进行比较如果经过城市k的路径长度更短则更新dist[i][j]因此就为dist[i][j]min(dist[i][k]dist[k][j],dist[i][j])因此对这个图执行n次上述操作(也就是插点法)得出的dist二维数组就为全源的最短路径。
代码模板
//dist[n][n]用来记录图中各点到各点的最短路径
void Floyd(int **dist){for(int k0;kn;k){for(int i0;in;i){for(int j0;jn;j){if(dist[i][k]dist[k][j]dist[i][j]){dist[i][j]dist[i][k]dist[k][j];}}}}
}例题部分代码
具体可看力扣1334. 阈值距离内邻居最少的城市只包含求解全源最短路径代码
#include iostream
#include cstring
#include vector
using namespace std;void Floyd(int n, vectorvectorint edges){const int INF0x3f3f3f3f;int dist[n][n];memset(dist,INF, sizeof(dist));for(int i0;in;i){dist[i][i]0;}for(auto edge:edges){dist[edge[0]][edge[1]]edge[2];dist[edge[1]][edge[0]]edge[2];}//Floyd算法计算全源最短路代码for(int k0;kn;k){for(int i0;in;i){for(int j0;jn;j){if(dist[i][k]dist[k][j]dist[i][j]){dist[i][j]dist[i][k]dist[k][j];}}}}for(int i0;in;i){cout第i城市到其他城市最短路径;for(int j0;jn;j)cout(i,j,dist[i][j]) ;coutendl;}
}int main() {vectorvectorintedges{{0,1,2},{0,4,8},{1,2,3},{1,4,2},{2,3,1},{3,4,1}};Floyd(5,edges);system(pause);return 0;
}尾言
完整版笔记也就是数据结构与算法专栏完整版可到我的博客进行查看或者在github库中自取(包含源代码) 博客1 codebooks.xyz博客2moonfordream.github.iogithub项目地址Data-Structure-and-Algorithms
