精华内容
下载资源
问答
  • K短路
    千次阅读
    2018-05-11 23:59:34

    其实这个才是最短路的一个非常好的应用。那么下面我们就来讲一讲具体如何实现吧。

    先确保自己已经熟练掌握了两种最短路的求解方法!!!

    这里有传送门:

    1、SPFA

    2、Dijsktra priority!

    然后我们先大体讲一讲思路,第k短路顾名思义就是我们要找到反正不是最短的一条路,那怎么办呢?我们这个时候就会发现我们不能像实现各种最短路算法的方法一样刷dis刷出第k短路,那么这个时候又怎么办呢,那么我们的A*算法就闪亮登场了!

    A*又叫启发式搜索,启发式搜索(Heuristically Search)又称为有信息搜索(Informed Search),它是利用问题拥有的启发信息来引导搜索,达到减少搜索范围、降低问题复杂度的目的,这种利用启发信息的搜索过程称为启发式搜索。

    这里给大家放两个照片,俗话说的好没有对比就没有伤害。
    我们直观对比一下普通搜法和A*搜法的差异(灰色是障碍物)

    因为图片有一些问题,所以这里并没有展出

    这里有个传送门:大家可以看一下里面有图有真相:
    戳我

    好了,我们下面来讲一讲A_star是如何实现K短路的吧。

    首先,我们要先存储两个图一个正图一个反图,用反图跑一遍最短路(spfa或Dijsktra随你便)记录好每一个点到达最后一个点的距离(dis数组存储) 然后干好这些事情以后我们可以开始我们的A_star算法了!

    大体思路其实是这样的,我们用所存储的条件从dis[1]开始push到优先队列中去然后每一次对优先队列中的边进行松弛操作即用当前的值减去当前位置的dis+正图到下一个点的连线+下一个点的dis

            q.push((sd){edge[now.num][i].num,now.len-dis[now.num]+edge[now.num][i].len+dis[edge[now.num][i].num]});
    

    大家应该没有什么理解上的问题了,下面我们上一篇代码!!!

    代码如下:(注意标注了important的地方!)

    #include<bits/stdc++.h>
    using namespace std;
    const int maxd=5010;
    int dis[maxd];
    bool vis[maxd];
    int n,m,e;
    struct sd {
        int num, len;
        bool operator < (const sd &other) const {
            return len > other.len;
        }
    };
    vector<sd> edge[maxd],redge[maxd];
    
    void spfa()
    {
        memset(dis,127,sizeof(dis));
        dis[e]=0;
        queue<int> q;
        q.push(e);
        vis[e]=true;
        while(!q.empty())
        {
            int now=q.front(); q.pop(); vis[now]=false;
            for(int i=redge[now].size()-1;i>=0;--i)
            {
                if(dis[redge[now][i].num]>dis[now]+redge[now][i].len)
                dis[redge[now][i].num]=dis[now]+redge[now][i].len;
                if(!vis[redge[now][i].num])
                {
                    vis[redge[now][i].num]=true;
                    q.push(redge[now][i].num);
                }
            }
        }
    }
    int A_star(int cnt)
    {
        int ccnt=0;
        priority_queue<sd> q;
        q.push((sd){1,dis[1]});//important
        while(!q.empty())
        {
            sd now=q.top();
            q.pop();
            if(now.num==e)
            {
                ccnt++;
                if(cnt==ccnt)
                {
                    return now.len;
                }
                continue;//important
            }
            for(int i=edge[now.num].size()-1;i>=0;--i)
            {
                q.push((sd){edge[now.num][i].num,now.len-dis[now.num]+edge[now.num][i].len+dis[edge[now.num][i].num]});//important
            }
        }
    }
    int main()
    {
        int us;
        scanf("%d%d%d",&n,&m,&e);
        scanf("%d",&us);
        int a,b,c;
        for(int i=1;i<=m;++i)
        {
            scanf("%d%d%d",&a,&b,&c);
            edge[a].push_back((sd){b,c});
            redge[b].push_back((sd){a,c});
        }
        spfa();
        if(us==1) goto flag;
        cout<<A_star(us); return 0;
        flag:
        printf("%d",dis[1]);
        return 0;
    }
    /*
    4 5 4
    3
    1 2 4
    2 3 2
    1 3 5
    3 4 6
    2 4 3
    */

    谢谢采纳!

    更多相关内容
  • 物流路径优化K短路matlab程序,可以运行,在此平台分享大家一起学习
  • 物流路径优化K短路matlab程序,可以运行,在此平台分享大家一起学习
  • k短路算法,有算法的说明和程序的源码
  • K短路的模板

    2014-09-24 17:31:44
    A* dijstra k短路 求法:反向建边 通过dijstra做预处理 最短路作为A*的评估函数 通过A* 将目标点出队列K次 如果原点和终点相同出栈K+1次
  • 在图论里,最短路,次短路,k短路的问题很常见。 这里总结一下。 存图技巧 数据小,稠密图的一般用邻接矩阵 稀疏图,数据大一般用邻接表(vector,链式前向星都可) 邻接矩阵 const int maxn = 1e5+5; int Graph[maxn]...

    在图论里,最短路,次短路,k短路的问题很常见。
    这里总结一下。

    存图技巧

    数据小,稠密图的一般用邻接矩阵
    稀疏图,数据大一般用邻接表(vector,链式前向星都可)

    邻接矩阵

    const int maxn = 1e5+5;
    int Graph[maxn][maxn];	// 正权图可以初始化成-1来判断是否连通,负权图可以再考虑开个数组或者用一个很大的值。
    

    链式前向星

    const int maxn = 1e5+5;
    struct Edge{
    		int u,v,nxt;
    }edge[maxn];
    int head[maxn],tot;
    inline void addedge(int u,int v,int w){	// u->v 权值是w
    		edge[++tot] = {u,v,w};
    		head[u] = tot;
    }
    

    最短路

    一般最短路算法有 BFS(暴力,一般只适用于点数小的情况),dijiastra(解决正权图),spfa(解决负权图,但容易死,被卡),floyed(解决点与点之间的最短距离问题,dp)

    这里直接给出单源最短路的算法(因为都挺好理解的) (重点在于松弛操作!)

    dijiastra

    // 堆优化版本
    const int maxn = 1e5+5;
    struct Edge{
        int u,v,nxt,w;
    }edge[maxn];
    int head[maxn],tot;
    inline void init(){
        memset(head,-1,sizeof(head));
    }
    inline void addedge(int u,int v,int w){
        edge[++tot] = {u,v,head[u],w};
        head[u] = tot;
    }
    int dis[maxn];  bool vis[maxn];
    inline void dijiastra(int s){
        struct Node{
            int u,dis;
            bool operator <(const Node &h)const{
                return dis > h.dis;
            }
        };
        memset(dis,0x3f,sizeof(dis));   //  视具体情况而定初始化的值
        dis[s] = 0;
        priority_queue<Node> pq;    pq.push(Node{s,0});
        while(!pq.empty()){
            Node u = pq.top();  pq.pop();
            if(vis[u.u])    continue;
            vis[u.u] = true;
            for(int i = head[u.u]; ~i; i = edge[i].nxt){
                Edge &e = edge[i];
                if(dis[e.v] > u.dis + e.w){
                    dis[e.v] = u.dis + e.w;
                    pq.push(Node{e.v,dis[e.v]});
                }
            }
        }
    }
    

    spfa

    struct Edge{
        int v,d;
        Edge(int vv,int dd):v(vv),d(dd){}
    };
    struct Node{
        int u,cost;
        Node(int uu,int cc):u(uu),cost(cc){}
        bool operator < (const Node & h)const{
            return cost > h.cost;
        }
    };
    const int MAX = 1e5+5;
    vector < Edge > edges;
    vector < int > Graph[MAX];
    bool vis[MAX];
    int dp[MAX];
    void AddEdge(int u,int v,int dis){
        edges.push_back(Edge{v,dis});
        Graph[u].push_back(edges.size()-1);
    }
    void SPFA(int s,int n){
        memset(dp,0x3f,sizeof(dp));
        dp[s-1] = 0;
        priority_queue<Node>q ;
        q.push(Node{s-1,0});  vis[s-1] = 1;
        while(!q.empty()){
            Node x = q.top(); q.pop();
            int u = x.u; vis[u] = 0; // cancel the tag;
            for(int i = 0; i < Graph[u].size(); ++i ){
                Edge & e = edges[Graph[u][i]];
                if( dp[e.v] > dp[u]+ e.d ){
                    dp[e.v] = dp[u] + e.d;
                    if(!vis[e.v]) q.push(Node{e.v,dp[e.v]});
                      vis[e.v] = 1;
                }
            }
        }
    }
    

    次短路(利用最短路来求)

    目前见到的方法一般有两种,遍历or删边

    1.删边。
    首先使用最短路算法求出 s − t s - t st的最短路,并且记录下最短路的路径(在松弛的时候记录前驱),然后对于这条路径,我们依次去删去一条边,然后跑最短路,去更新ans

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5+5;
    const double inf = 1e9+5;
    struct Edge{
        int u,v,nxt;    double w;
    }edge[maxn];
    int head[maxn],tot;
    pair<int,int> path[maxn];
    inline void addedge(int u,int v,double w){
        edge[++tot] = {u,v,head[u],w};
        head[u] = tot;
    }
    inline void init(){
        memset(head,-1,sizeof(head));
        tot = 0;
    }
    
    double dis[maxn];   bool vis[maxn];
    bool isok[maxn];
    inline void dijiastra(int s){
        struct Node{
            int u;  double dis;
            bool operator <(const Node &h)const{
                return dis > h.dis;
            }
        };
        for(int i = 0; i < maxn; ++i)  dis[i] = inf,vis[i] = false;
        priority_queue<Node> pq;    pq.push(Node{s,0});
        while(!pq.empty()){
            Node u = pq.top();  pq.pop();
            if(vis[u.u])
                continue;
            vis[u.u] = true;
            for(int i = head[u.u]; ~i; i = edge[i].nxt){
                if(isok[i]) continue;
                Edge &e = edge[i];
                if(dis[e.v] > u.dis + e.w){ //  松弛过程中记录
                    dis[e.v] = u.dis + e.w;
                    path[e.v] = make_pair(u.u,i);
                    pq.push(Node{e.v,dis[e.v]});
                }
            }
        }
    }
    struct Point{
        int x,y;
    }p[maxn];
    inline double get_dis(const Point &p,const Point&q){
        return sqrt( (p.x-q.x)*(p.x-q.x) + (p.y-q.y)*(p.y-q.y));
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0); cout.tie(0);
        init();
        int n,m;    cin >> n >> m;
        for(int i = 1; i <= n; ++i) cin >> p[i].x >> p[i].y;
        for(int i = 0,u,v; i < m; ++i){
            cin >> u >> v;  double d = get_dis(p[u],p[v]);
            addedge(u,v,d); addedge(v,u,d);
        }
        dijiastra(1);
        pair<int,int> tt = path[n];
        vector<int> ee; ee.push_back(tt.second);
        while(tt.first!=1){
            tt = path[tt.first];
            ee.push_back(tt.second);
        }
    
        double ans = inf;
        for(int i = 0; i < ee.size(); ++i){
            isok[ee[i]] = true;
            dijiastra(1);
            isok[ee[i]] = false;
            ans = min(ans,dis[n]);
        }
        if(ans==inf){
            cout << -1 << endl;
        }
        else cout <<fixed<<setprecision(2)<< ans << endl;
        return 0;
    }
    
    

    2.遍历。
    跑两次最短路,分别是以起点,以终点。 然后遍历所有边,去更新长度
    ∑ e ( u , v ) ∈ G ( v , e ) m i n ( d i s [ 1 ] [ u ] + w ( u , v ) + d i s [ v ] [ n ] ) \sum_{e(u,v)\in G(v,e)}min(dis[1][u]+w(u,v)+dis[v][n]) e(u,v)G(v,e)min(dis[1][u]+w(u,v)+dis[v][n])

    k短路 ( A*或者左偏树)(当然也可以用于解决次短路问题)

    左偏树,A*待更新

    左偏树学习:大佬博客

    展开全文
  • 图论 —— k 短路

    千次阅读 2019-10-11 15:17:56
    所谓 k 短路问题,是指给定一个具有 n 个点 m 条边的带正权有向图,再给定起点 S 与终点 T,询问从 S 到 T 的所有权和中,第 k 短的路径的长度。 k 短路问题的解决方法有两种,一种是利用A*算法求解,另一种是利用...

    【概述】

    所谓 k 短路问题,是指给定一个具有 n 个点 m 条边的带正权有向图,再给定起点 S 与终点 T,询问从 S 到 T 的所有权和中,第 k 短的路径的长度。

    k 短路问题的解决方法有两种,一种是利用A*算法求解,另一种是利用最短路算法与可持久化堆结合求解。

    【A*算法】

    对于 Dijkstra 算法,有一个结论是:当一个点第 k 次出队的时候,此时路径长度就是 s 到它的第 k 短路

    但直接来写会造成 MLE,因此要利用 A* 算法来优化状态数。

    首先建立反图,跑一次最短路算法,得到每个点到 t 的最短路的距离,然后用当前走的距离加上终点的最短路长度作为优化级来进行 A*

    因此,当一个点第 k 次出队时,答案为这个点的优先级,当终点第 k 次出队时,答案为这个点已走的路径

    struct Edge {
        int to, next;
        int w;
        Edge() {}
        Edge(int to, int next, int w) : to(to), next(next), w(w) {}
    };
    struct Map {
        int tot;
        int head[N];
        Edge edge[N * N];
        Map() {
            tot = 0;
            memset(head, -1, sizeof(head));
        }
        void addEdge(int x, int y, int w) {
            edge[++tot].to = y;
            edge[tot].next = head[x];
            edge[tot].w = w;
            head[x] = tot;
        }
        Edge &operator[](int pos) { return edge[pos]; }
    };
    int n, m;
    Map G, GT;
    int dis[N];
    bool vis[N];
    struct Status{
        int node;//点编号
        int diss;//距离
        int priority;//优先级
        Status() : node(0), diss(0), priority(dis[0]) {}
        Status(int node, int diss) : node(node), diss(diss), priority(diss + dis[node]) {}
        bool operator<(Status b) const { return priority > b.priority; }
    } status;
    bool SPFA(int S, int T, int k) { //对反图求最短路
        memset(dis, INF, sizeof(dis));
        memset(vis, false, sizeof(vis));
        dis[S] = 0;
    
        queue<int> Q;
        Q.push(S);
        while (!Q.empty()) {
            int x = Q.front();
            Q.pop();
            vis[x] = false;
            for (int i = GT.head[x]; i != -1; i = GT[i].next) {
                int y = GT[i].to;
                if (dis[x] + GT[i].w < dis[y]) {
                    dis[y] = dis[x] + GT[i].w;
                    if (!vis[y]) {
                        Q.push(y);
                        vis[y] = true;
                    }
                }
            }
        }
        return dis[T] != INF;
    }
    int label[N];
    int AStar(int S, int T, int k) {
        memset(label, 0, sizeof(label));
        if (S == T)
            k++;
    
        priority_queue<Status> Q;
        Q.push(Status(S, 0));
        while (!Q.empty()) {
            Status temp = Q.top();
            Q.pop();
            label[temp.node]++;
            if (temp.node == T && label[temp.node] == k)
                return temp.diss;
            for (int i = G.head[temp.node]; i != -1; i = G[i].next)
                if (label[G[i].to] < k)
                    Q.push(Status(G[i].to, temp.diss + G[i].w));
        }
        return -1;
    }
    int main() {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i++) {
            int x, y, w;
            scanf("%d%d%d", &x, &y, &w);
            G.addEdge(x, y, w);
            GT.addEdge(y, x, w);
        }
    
        int s, t, k;
        scanf("%d%d%d", &s, &t, &k);
        if (!SPFA(t, s, k))
            printf("-1\n");
        else
            printf("%d\n", AStar(s, t, k));
        return 0;
    }

    【可持久化堆】

    考虑建立反图,然后跑最短路算法得到以 T 为根的最短路径生成树,当走一条非树边 (u,v) 时,最终的路径长度就会因此增加 dis[v]-dis[u]+w

    对于一条路径,我们依次将它经过的非树边记下来,约定得到的序列是这条路径的非树边序列。

    考虑对于一个合法的非树边序列,我们可以找到唯一的一条 S 到 T 的路径与之对应,因此,k 短路的长度就等于第 k 小的代价和加上 S 到 T 的最短路长度。

    考虑如何来得到一个合法的非树边序列:

    1. 找到一条起点在当前点 p 到根 t 的路径上的非树边
    2. 令 p 等于这条边的终点

    我们可以通过这样的方法来得到所有的非树边序列,但是我们并不需要所有的非树边序列,因此当找到第 x 短路后再拓展状态,然后用优先队列来维护,但这样每次拓展时间复杂度可达 O(m),总时间复杂度可以达到 O(mklog⁡(mk))。

    这样时间复杂度太高,令人无法接受,因为其中被用到的状态十分少,由于当一个非树边序列出队时,代价和比它大的才可能有用,因此,考虑一个非树边序列出队时通过下面的方法来进行得到新的序列:

    1. 追加操作:假如最后一条非树边的终点为 v,找到一条起点在 v 到 t 的路径上代价最小的非树边追加在当前非树边序列后
    2. 替换操作:将最后一条非树边更换为代价比它大的 1 条非树边

    如下图,橙色虚线是被替换掉的非树边,紫色是新加入的非树边

    考虑用一些可持久化数据结构来维护起点在点 u 到根的路径上的非树边的代价,对于替换操作,当使用可持久化堆时,把最后一条非树边替换为它所在的堆中它的左右子节点代表的边

    struct Node{
        int val,to;
        Node *left,*right;
        Node(){}
        Node(int val, int to, Node *left, Node *right) : val(val), to(to), left(left), right(right) {}
    };
    #define Limit 1000000
    Node pool[Limit];
    Node *top = pool;
    Node *newNode(int val, int to) {
        if (top >= pool + Limit)
            return new Node(val, to, NULL, NULL);
        top->val = val;
        top->to = to;
        top->left = NULL;
        top->right = NULL;
        return top++;
    }
    Node *meGTe(Node *a, Node *b) {
        if (!a)
            return b;
        if (!b)
            return a;
        if (a->val > b->val)
            swap(a, b);
        Node *p = newNode(a->val, a->to);
        p->left = a->left;
        p->right = a->right;
        p->right = meGTe(p->right, b);
        swap(p->left, p->right);
        return p;
    }
    struct Status {
        int dist;
        Node *p;
        Status(){}
        Status(int dist, Node *p) : dist(dist), p(p) {}
        bool operator<(Status b) const { return dist > b.dist; }
    };
    struct Edge {
        int to, next;
        int w;
        Edge() {}
        Edge(int to, int next, int w) : to(to), next(next), w(w) {}
    };
    struct Map {
        int tot;
        int *head;
        Edge *edge;
    
        Map() {}
        Map(int n, int m) : tot(0) {
            head = new int[(n + 1)];
            edge = new Edge[(m + 5)];
            memset(head, 0, sizeof(int) * (n + 1));
        }
        void addEdge(int x, int y, int w) {
            edge[++tot].to = y;
            edge[tot].next = head[x];
            edge[tot].w = w;
            head[x] = tot;
        }
        Edge &operator[](int pos) { return edge[pos]; }
    };
    int n, m;
    int s, t, k;
    Map G, GT;
    bool *vis;
    int *dis, *pre;
    queue<int> SPFA(int S) {
        vis = new bool[(n + 1)];
        dis = new int[(n + 1)];
        pre = new int[(n + 1)];
    
        memset(dis, INF, sizeof(int) * (n + 1));
        memset(vis, false, sizeof(bool) * (n + 1));
    
        queue<int> Q;
        Q.push(S);
        dis[S] = 0;
        pre[S] = 0;
        while (!Q.empty()) {
            int x = Q.front();
            Q.pop();
            vis[x] = false;
            for (int i = GT.head[x]; i; i = GT[i].next) {
                int y = GT[i].to;
                int w = GT[i].w;
                if (dis[x] + w < dis[y]) {
                    dis[y] = dis[x] + w;
                    pre[y] = i;
                    if (!vis[y]) {
                        vis[y] = true;
                        Q.push(y);
                    }
                }
            }
        }
        return Q;
    }
    Node **Hash;
    void rebuild(queue<int> Q) { //建堆
        for (int i = 1; i <= n; i++) {
            for (int j = G.head[i]; j; j = G[j].next) {
                int to = G[j].to;
                if (pre[i] != j)
                    G[j].w += dis[to] - dis[i];
            }
        }
    
        Hash = new Node *[(n + 1)];
        Q.push(t);
        Hash[t] = NULL;
        while (!Q.empty()) {
            int x = Q.front();
            Q.pop();
            if (pre[x])
                Hash[x] = Hash[G[pre[x]].to];
            for (int i = G.head[x]; i; i = G[i].next)
                if (pre[x] != i && dis[G[i].to] != INF)
                    Hash[x] = meGTe(Hash[x], new Node(G[i].w, G[i].to, NULL, NULL));
    
            for (int i = GT.head[x]; i; i = GT[i].next) {
                int y = GT[i].to;
                if (pre[y] == i)
                    Q.push(y);
            }
        }
    }
    int kthPath(int k) {
        if (s == t)
            k++;
        if (dis[s] == INF)
            return -1;
        if (k == 1)
            return dis[s];
    
        priority_queue<Status> Q;
        if (!Hash[s])
            return -1;
    
        Q.push(Status(Hash[s]->val, Hash[s]));
        while (--k && !Q.empty()) {
            Status x = Q.top();
            Q.pop();
    
            if (k == 1)
                return x.dist + dis[s];
    
            int y = x.p->to;
            if (Hash[y])
                Q.push(Status(x.dist + Hash[y]->val, Hash[y]));
            if (x.p->left)
                Q.push(Status(x.dist - x.p->val + x.p->left->val, x.p->left));
            if (x.p->right)
                Q.push(Status(x.dist - x.p->val + x.p->right->val, x.p->right));
        }
        return -1;
    }
    int main() {
        scanf("%d%d", &n, &m);
        G = Map(n, m);
        GT = Map(n, m);
        for (int i = 1, u, v, w; i <= m; i++) {
            scanf("%d%d%d", &u, &v, &w);
            G.addEdge(u, v, w);
            GT.addEdge(v, u, w);
        }
        scanf("%d%d%d", &s, &t, &k);
        queue<int> Q = SPFA(t);
        rebuild(Q);
        printf("%d\n", kthPath(k));
        return 0;
    }

    【例题】

    • Remmarguts' Date(POJ-2449)(SPFA+A*)点击这里
    • Remmarguts' Date(POJ-2449)(SPFA+可持久化堆)点击这里
    展开全文
  • k短路和次短路

    千次阅读 多人点赞 2018-09-08 16:25:19
    求某点s到某点e的第k短路就是k短路问题 2.思路: (1)我们知道在BFS中,第一次到达终点就是到终点的最短路,那么第k次到达终点,当然就是到终点的第k短路了。但是如果直接BFS搜索下去,时间复杂度会非常高,因此...

    一.求第k短路

    1.什么是第k短路?第一短路就是最短路,以此类推。求某点s到某点e的第k短路就是k短路问题

    2.思路:

    (1)我们知道在BFS中,第一次到达终点就是到终点的最短路,那么第k次到达终点,当然就是到终点的第k短路了。但是如果直接BFS搜索下去,时间复杂度会非常高,因此我们需要剪枝,怎么剪枝呢?

    (2)我们每次只需要取出每次到达终点最有希望的路径,就避开了一些没有意义的到其他点的路径。因此我们需要一个启发函数。令f = x + h(其中x为到当前点的实际距离,h为从当前点到达终点的估测最短距离),则f就估测为从起点到终点的路径长度,我们每次只要有目的有方向的前进到达终点k次即为k短路

    (3)那么怎么求这个h呢?h其实为每个点到达终点的最短路,但是我们只学过某个点到其他点的最短路怎么办?当然是把终点当作起点跑最短路啊(哇笨蛋) , 但是这里有一个问题:我们需要在跑终点最短路时使用反向边,跑BFS时使用正向边(有向图),为什么呢:

     

    (起点1,终点2)

    我们如果跑终点最短路使用正向边,2是到不了1的,所以在跑BFS时,从1到2的估测函数是不存在的,但是事实是存在的。所以我们这里应该使用反向建边。而跑BFS时当然是使用正向边。

    也就是说,终点反向建边能到达的点,正向边时才是能过来的点



    3.求解步骤

    (1)Dijkstra求终点到其他点的最短路

    (2)正向边跑起点的BFS(以A*启发函数:f = x + h为排序,取出点)

    4.代码:(poj2449)板子:

    #include <iostream>
    #include<bits/stdc++.h>
    using namespace std;
    #define INF 0x3f3f3f3f
    typedef long long LL;
    typedef pair<LL,int> P;
    const int maxn = 1000 + 7;
    struct Edge{//正向边
        int to,next;
        LL val;
    }edge[maxn*100];
    struct Line{//反向边
        int to,next;
        LL val;
    }line[maxn*100];
    int n,m,s,e,tot,k,head[maxn],revhead[maxn];
    int tot2;
    bool vis[maxn];
    LL dist[maxn];//保存终点到其他点的最短路
    inline void addEdge(int a,int b,LL c){//正向建边
        edge[tot].to = b;edge[tot].next =  head[a];edge[tot].val = c;head[a] = tot++;
    }
    inline void AddEdge(int a,int b,LL c){//反向建边
       line[tot2].to = b;line[tot2].next = revhead[a];line[tot2].val = c;revhead[a] = tot2++;
    }
    struct Node{//BFS保存状态
       int to;
       LL cost;
       bool operator <(const Node&another)const{//排序规则按照估价函数大小由小到大
            return cost + dist[to] > another.cost + dist[another.to];//估价= 当前 + 到终点最短
       }
       Node(int a,LL c):to(a),cost(c) {}
    };
    inline void Dijkstra(int a){//最短路
       dist[a] = 0;
       priority_queue<P,vector<P>,greater<P> >que;
       que.push(P(0,a));
       while(!que.empty()){
           P p = que.top();
           que.pop();
           if(vis[p.second])continue;
           vis[p.second] = 1;
           LL num = p.first;
           for(int i = revhead[p.second];~i;i = line[i].next){//跑反向边
               if(!vis[line[i].to]&&dist[line[i].to] > num + line[i].val){
                   dist[line[i].to] = num + line[i].val;
                   que.push(P(dist[line[i].to],line[i].to));
               }
           }
       }
    }
    inline LL BFS(int a){//BFS
       priority_queue<Node> que;
       que.push(Node(a,0));
       while(!que.empty()){
          Node node = que.top();
          que.pop();
          if(node.to==e){//到达终点次数
             k--;
             if(k==0){
                return node.cost;
             }
          }
          for(int i = head[node.to];~i;i = edge[i].next){//扩散(跑反向边)
               que.push(Node(edge[i].to,node.cost + edge[i].val));
          }
       }
       return -1;
    }
    int main()
    {
        while(scanf("%d%d",&n,&m)!=EOF){
            tot = tot2 = 0;
            memset(dist,INF,sizeof(dist));
            memset(vis,0,sizeof(vis));
            memset(head,-1,sizeof(head));
            memset(revhead,-1,sizeof(revhead));
            for(int i = 0;i<m;i++){
                int a,b;
                LL v;
                scanf("%d%d%lld",&a,&b,&v);
                addEdge(a,b,v);
                AddEdge(b,a,v);
            }
            scanf("%d%d%d",&s,&e,&k);//起点 + 终点 + k短路
            Dijkstra(e);
            if(dist[s]==INF){
                printf("-1\n");
                continue;
            }
            if(s==e)k++;//起点终点重合,排除0距离
            LL ans = BFS(s);
            printf("%lld\n",ans);
        }
        return 0;
    }
    

     

     

    二.求次短路

    1.dist[ i ][ 0 ]表示到点 i 的最短路 , dist[ i ][ 1 ]表示到点 i 的次短路

    2.

    最短路何时更新:当dist[ i ][ 0 ] > len(j) + val( j , i )时,直接更新最短路

    何时更新次短路:   dist[ i ][ 0 ]  < len(j) + val( j , i )  < dist[ i ][ 1 ]时,更新次短路

    3.代码:

    #include <iostream>
    #include<bits/stdc++.h>
    using namespace std;
    #define INF 0x3f3f3f3f
    typedef pair<int,int>P;
    const int maxn = 100000 + 7;
    struct Edge{
       int to,next,val;
    }edge[maxn];
    int n,m,head[maxn],dist[maxn][2],tot;
    void addEdge(int a,int b,int c){
       edge[tot].to = b;edge[tot].val = c;edge[tot].next = head[a];head[a] = tot++;
    }
    void Dijkstra(int s){
        for(int i = 0;i<=n;i++)dist[i][0] = dist[i][1] = INF;
        dist[s][0] = 0;
        priority_queue<P,vector<P>, greater<P> >que;
        que.push(P(0,s));
        while(!que.empty()){
            P p = que.top();
            que.pop();
            if(p.first > dist[p.second][1])continue;
            for(int i = head[p.second];~i;i = edge[i].next){
                int d = p.first + edge[i].val;
                 if(dist[edge[i].to][0] > d){//更新最短路
                    swap(dist[edge[i].to][0] , d);//交换!!!
                    que.push(P(dist[edge[i].to][0],edge[i].to));//注意d值已经被交换了
                 }
                 if(dist[edge[i].to][1] > d&&dist[edge[i].to][0] < d){//更新次短路
                    dist[edge[i].to][1] = d;
                    que.push(P(d,edge[i].to));
                 }
            }
        }
    }
    int main()
    {
        tot = 0;
        memset(head,-1,sizeof(head));
        scanf("%d%d",&n,&m);
        for(int i = 0;i<m;i++){
            int a,b,v;
            scanf("%d%d%d",&a,&b,&v);
            addEdge(a,b,v);
            addEdge(b,a,v);
        }
        int s,t;
        scanf("%d%d",&s,&t);
        Dijkstra(s);
        printf("%d %d\n",dist[t][0],dist[t][1]);
        return 0;
    }
    

     

    展开全文
  • 对于简单图,K短路,是指的起点s到终点t的第K个最短路径
  • K短路分为有限制的K短路和无限制的K短路,有限制的K短路是指求得的路径中不含有回路(路径上任何一个节点的出现次数不大于1次),无限制的K短路则对求得的路径中没有要求,这篇博客讨论后者。 本篇博客使用的图例如...
  • K短路 A*

    2019-04-20 09:55:14
    一、k短路 什么是k短路?最短路就是第一短路,那么第k短的就是k短路。 二、求k短路 首先可以想到在BFS中,从起点开始走,把每个点放入队列中时,以当前走过的距离加上当前点到终点的最短距离的和(即我们假设可以...
  • k短路问题就是最短路问题的延申,要找出第k短的路径。用广搜进行路径查找,第一次找到的就是最短路,第二次找到的是第2短路…以此类推。所以我们只需要一直广搜直到找到k次终点,这时即为第k短路。 但直接暴力广搜会...
  • A*是一种启发式搜索,根据目标地点和当前点的距离和估计要走的步数来决策下一步走哪个方向。而这两个参数,一般用g(x)g(x)和h(x)h(x),其中g(x)g(x)为xx点到目标点的实际距离。...而k短路,就是终点第K次被找到的时候。
  • 最短路,即第1短路有很多种求法,SPFA,Dijkstra等,但第k短路怎么求呢?其实也是基于Dijkstra;因为Dijkstra用的是堆优化,这样保证每次弹出来的都是最小值,只是求最短路只是弹出一次就返回了,我们可以用Dijkstra...
  • 图论- k 短路.rar

    2021-09-16 22:49:38
    图论- k 短路.rar
  • K短路——A*算法

    2018-08-20 16:11:01
    实际上,就是预处理终点到起点的最短路,再在起点到终点时判断第KKK短路。 这是一个非常实用的解决第KKK短路问题的算法。 常规操作: - 先预处理出终点到起点(反图)的最短路(SPFA,Dijs) - 再通过优...
  • K短路(A*)

    2019-10-27 22:41:34
    给定一张N个点(编号1,2…N),M条边的有向图,求从起点S到终点T的第K短路的长度,路径允许重复经过点或边。 注意: 每条最短路中至少要包含一条边。 输入格式 第一行包含两个整数N和M。 接下来M行,每行包含三个...
  • K短路的几种求法

    2018-10-17 09:16:28
    K短路 引入 对于最短路,我们可以用Dijstra,Spfa,Floyd\rm Dijstra,Spfa,FloydDijstra,Spfa,Floyd等算法求出。 那么对于第KKK短的路,我们该如何求取呢? Ps. 这里都是在有向图上求取KKK短路,无向图上可以将其建为...
  • 问题 给定一张N个点(编号1,2…N),M条边的有向图,求从起点S到终点T的第K短路的长度,路径允许重复经过点或边。 注意:每条最短路中至少...输出占一行,包含一个整数,表示第K短路的长度,如果第K短路不存在,则...
  • 1. 问题描述: 给定一张 N 个点(编号 1,2…N),M 条边的有向图,求从起点 S 到终点 T 的第 K 短路的长度,路径允许重复经过点或边。...输出占一行,包含一个整数,表示第 K 短路的长度,如果第 K 短路不存在,则
  • k短路算法-word

    2018-02-07 16:46:08
    在最短路算法基础上编制的k短路算法,简洁方便,很容易套用
  • 本资源是http://write.blog.csdn.net/postedit/50428251 进阶01——考虑换乘的基于路径长度的所有点间K短路算法的计算结果。
  • Yen算法求前K短路

    2010-09-01 22:14:26
    Yen算法求前K短路,无向图中求Yen算法求前K短无环路。
  • A-star和第k短路和次小生成树和Yen和MPS寻路算法.doc
  • 找第K短路 c++ 图论

    2013-08-06 16:23:22
    这是运用C++求出来的第k短路,属于图论
  • astar 第k短路

    2011-11-15 17:54:18
    astar 启发式搜索求第k短路。主要运用的贪心加优先队列的思想。
  • [jzoj1163]第k短路

    2017-10-10 09:06:49
    DescriptionBessie 来到一个小农场,有时她想回老家看看她的一位好友。她不想太早地回到老家,因为她喜欢途中的美丽风景。她决定选择K短路径,而不是最短路径。 农村有 R (1≤R≤100,000) 条单向的路,...K短路的定义
  • 综合算法05—考虑换乘的K短路算法

    千次阅读 2016-12-12 20:12:19
    求满足条件的K短路。 二、算法描述 1.K短路算法: Step1:令k=1,求出最短路,并加上t换乘; Step2:k=k+1,求出k短路,并加上t换乘; Step3:判断,if是有效路径,保存并转Step2;else...
  • A*算法——第K短路

    千次阅读 2017-08-15 20:50:08
    例题JZOJ senior 1163第K短路题目描述Bessie 来到一个小农场,有时她想回老家看看她的一位好友。她不想太早地回到老家,因为她喜欢途中的美丽风景。她决定选择K短路径,而不是最短路径。 农村有 R (1≤R≤100,000) ...
  • K短路+严格第K短路

    千次阅读 2019-10-12 20:20:52
    所谓K短路,就是从s到t的第K短的路,第1短就是最短路。 如何求第K短呢?有一种简单的方法是广度优先搜索,记录t出队列的次数,当t第k次出队列时,就是第k短路了。但点数过大时,入队列的节点过多,时间和空间复杂度...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 70,133
精华内容 28,053
关键字:

k短路

友情链接: Desktop.rar