链式前向星

一种存储图的数据结构

建立一个结构体和一个数组加一个变量,这里的to代表边\((u,v)\)中的\(v\)结点,而\(edge\)数组的索引\(idx\)代表\(u\),其中\(w\)代表权值,\(next\)代表以\(u\)为起始点的上一个边。
\(head\)代表这个\(x\)结点在\(edge\)数组中的最后一个边的下标索引,\(cnt\)用于记录边时当\(edge\)的下标索引用。

struct {
  int to, w, next;
} edge[MAX_N];
int head[MAX_N], cnt = 0;

为链式前向星添加边

  1. ++cnt为新添加的边选择一个空变量
  2. edge[++cnt].next=head[u]代表让\(edge[cnt]\)中的\(next\)变量指向\(u\)结点的上一个边
  3. \(head[u]=cnt\)代表更新结点\(u\)的最后一条边在\(edge\)中的下标
edge[++cnt].next=head[u];
edge[cnt].w=w;
edge[cnt].to=v;
head[u]=cnt;

遍历

首先获取结点\(x\)的最后一条边,经过数据处理后,将i移向结点\(x\)的上一条边

for(int i=head[x];i;i=edge[i].next)

SPFA算法

求最小单源路径

  1. 将源点放入队列中,并标志源点\(s\)已经在队列之中\(vis[s]=true\)
  2. 进入一个循环,当队列为空,各节点的最短路径便求出来了
  3. 从队列中取出一个结点,并更新标志,遍历该结点的边,对符合条件的各边\(dis[edge[i].to]>dis[v]+edge[i].w\)进行松弛,然后如果符合条件的松弛边目标结点如果未在队列中,则放入,更改标志。

松弛:对于每个顶点v∈V,都设置一个属性\(d[v]\),用来描述从源点s到v的最短路径上权值的上界,称为最短路径估计。就是这个操作\(dis[edge[i].to] = dis[v] + edge[i].w;\)

  queue<int> que;
  que.emplace(s);
  vis[s] = true;
  while (!que.empty()) {
    int v = que.front();
    que.pop();
    vis[v] = false;
    for (int i = head[v]; i; i = edge[i].next) {
      if (dis[v] + edge[i].w < dis[edge[i].to]) {
        dis[edge[i].to] = dis[v] + edge[i].w;
        if (!vis[edge[i].to]) {
          que.emplace(edge[i].to);
          vis[edge[i].to] = true;
        }
      }
    }
  }

求是否存在负环

如果一个图存在负环,那么其的最短路径一定会存在一个无限循环,经过负环后,路径越来越小,那么一定有一些结点,一直入队出队,判断是否有结点入队次数大于\(n\)

  queue<int> que;
  que.emplace(1);
  vis[1]=true,dis[1]=0;
  while (!que.empty()) {
    int v = que.front();
    que.pop();
    vis[v] = false;
    fe(ver, G[v]) if (dis[ver.to] > dis[v] + ver.cost) {
      dis[ver.to] = dis[v] + ver.cost;
      if (!vis[ver.to]) {
        if (++cnt[ver.to] >= n) {
            //存在负环
        }
        que.emplace(ver.to);
        vis[ver.to] = true;
      }
    }
  }

原文地址:http://www.cnblogs.com/GuanStudy/p/16920345.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性