最短路径 Dijkstra Floyd SPFA

最短路径

定义

从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径，称为最短路径

起因: 计蒜客 架设电线

  1. 问题思路: 利用二分不断求出最短路径长度的最小值
  2. 最短路径求法: 题解给的是 spfa: shortest path faster algorithm,
    是Bellman-Ford算法的队列优化算法的别称, 针对负权环, 用在其他图上, 容易卡数据,
    推荐最基础的Djikstra, 除此之外还有
  • Floyd算法(待学)
  • spfa(待学)
  • Djikstra

    Djikstra(基础版)

  • 特点: 使用广度优先搜索BFS
  • 思路:
  • 使用两个集合, vis 负责顶点访问标志, dis 负责实时更新顶点
  • 开始时 dis 只有源顶点, 且源顶点到每个顶点的距离为无穷大(infinity), 接着把所有与目前顶点连通的顶点, 纳入到dis中, 更新到新顶点的最短距离, 更新 vis 访问标志
  • 重复第二个动作, 直到所有顶点纳入到 dis 中
  • 实现 ```

    include

    include

    using namespace std;

const int INF = 10000; int edge[50][50]; int dis[50];//d表示源节点到该节点的最小距离 bool vis[50];//v标记访问过的节点 int n, m;//n代表点数 m代表边数 int main() { freopen(“in.txt”, “r”, stdin); scanf(“%d%d”, &n, &m); int min; int x, y, d; memset(edge, INF, sizeof(edge)); //使用一个值初始化无限大 memset(dis, INF, sizeof(dis)); memset(vis, false, sizeof(vis)); for(int i = 0; i < m;i++) { scanf(“%d%d%d”, &x, &y, &d); edge[x][y]=d; edge[y][x]=d; } dis[1]=0; //使用1作为源顶点 距离置0 //类似冒泡 for(int i = 1, k; i <= n; i++) { min = INF; for(int j = 1; j <= n; j++) { if(!vis[j] && dis[j] < min) { min = dis[j]; k = j; } } vis[k] = true; //松弛操作调整 for(int j = 1; j <= n; j++) { if(!vis[j] && edge[k][j] != INF && dis[j] > dis[k] + edge[k][j]) { dis[j] = dis[k] + edge[k][j]; }
} } //最终输出从源节点到其他每个节点的最小距离 for(int i = 1; i <= n; i++) printf(“%d->%d: %d\n”, 1, i, dis[i]); return 0; }

  1. ### Djikstra优化版
  2. - 原理和思路: 利用vector创建邻接表, 用优先队列保存路径, 自动完成排序<br />
  3. - 实现

include

include

include

include

using namespace std;

//定义邻接表 struct edge { int v, d; //顶点 权值 edge(int v, int d): //初始化 v(v), d(d) { } }; //优先队列生成最短路径结构体 struct queueelement { int v; int d; queue_element(int v, int disvalue): v(v), d(dis_value) { } bool operator <(const queue_element &other) const { return d > other.d; //重载操作符, 距离大的优先级靠后 } }; int dis[50]; bool vis[50]; vector edges[50]; int n, m;

void Djikstra(int v) { vis[v] = 1; priority_queue q; q.push(queue_element(v, 0));//首先把源顶点压入优先队列 

  1. while (!q.empty()) {
  2.     queue_element t = q.top();
  3.     q.pop();
  4.     if (vis[t.v]) {     
  5.         continue;    //如果已访问过则扔掉 继续下一个
  6.     }
  8.     vis[t.v] = true;//更新访问标志 
  9.     dis[t.v] = t.d; //保存路径 
  11.     //松弛操作 更新最短路径 
  12.     vector<edge>::iterator it;
  13.     for (it = edges[t.v].begin(); it != edges[t.v].end(); ++it) {
  14.         q.push(queue_element(it->v, t.d + it->d)); //压入顶点距离 自动排序 
  15.     }
  16. }
  18. //最终输出从源节点到其他每个节点的最小距离
  19. for(int i = 1; i <= n; i++){
  20.     if (i != v) {
  21.         printf("%d->%d:%d\n",v, i, dis[i]);
  22.     }
  23. }     
  24. cout << endl;

}

int main() { freopen(“in.txt”, “r”, stdin) ; scanf(“%d%d”,&n,&m); int x, v, d; //建立邻接表 for(int i=0;i<m;i++) { scanf(“%d%d%d”,&x,&v,&d); edges[x].push_back(edge(v, d)); edges[v].push_back(edge(x, d)); } //每个节点都当做一次源节点 Djikstra(1);

  1. return 0;

}

  1. ### SPFA普通队列实现

struct A { int y,time,next; } a[M<<1];

int pre[M],cent=0;//链式前向星数组 int vis[M], nums[M], dis[M] ; //vis 是否在队列 nums 入队次数超过n 返回-1 dis 1到其他点的距离 //SPFA int n; // 总点数 int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边 int dist[N]; // 存储每个点到1号点的最短距离 bool st[N]; // 存储每个点是否在队列中 // 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1 int spfa() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue q;
q.push(1); 

  1. st[1] = true;   
  3. while ( q.size() )    {        
  4.     auto t = q.front();        
  5.     q.pop();       
  6.     st[t] = false;        
  8.     for (int i = h[t]; i != -1; i = ne[i])  {            
  9.         int j = e[i];       
  11.         if (dist[j] > dist[t] + w[i]) {                
  12.             dist[j] = dist[t] + w[i];   
  14.             if (!st[j])  { // 如果队列中已存在j，则不需要将j重复插入                                    
  15.                 q.push(j);                    
  16.                 st[j] = true;               
  17.             }           
  18.         }       
  19.     }    
  20. }   
  21. if (dist[n] == 0x3f3f3f3f) return -1;    
  22. return dist[n];

}

```