Dijkstra 运行慢

Question

Spoj 中有一个名为 HIGHWAYS 的问题，基本上是找到 2 个给定城市之间的最短路径。

我第一次解决它，我使用了Dijkstra算法...我做对了，虽然代码有点大，所以我决定用较小的代码重做（显然是一样的），但它正在超出时间限制。

我想知道他们之间的区别是什么让这个 TLE 发生了。

输入是这样的：

n            //number of test cases
c e s e      //number of cities (from 1 to c), number of edges, start and end cities
c1 c2 w      //e lines, each with connection between c1 and c2 with weight w

这是长代码（已接受）：

#include <bits/stdc++.h>
using namespace std;

#define si(n) scanf("%d", &n)
#define INF 99999
int d[100010];

struct edge {
        int v, weight;

        edge(int a, int w) {
                v = a;
                weight = w;
        }

        bool operator < (const edge & o) const {
                return weight > o.weight;
        }

};

struct vertex {
        int value;
        vector <edge> adj;

        vertex() {
            adj.clear();
        }

        vertex(int val) {
                value = val;
                adj.clear();
        }

        void add(edge a) {
                adj.push_back(a);
        }
};

struct graph {
        vertex v[100010];

        void add_v(int val) {
                vertex a(val);
                a.adj.clear();
                v[val] = a;
        }
        void add_a(int v1, int v2, int p) {
                v[v1].add(edge(v2, p));
                v[v2].add(edge(v1, p));
        }

        void dijkstra(int n, int f) {
                for(int i = 0; i <= f; i++ ) d[i] = INF;
                priority_queue < edge > Q;
                d[n] = 0;
                int current;


                Q.push(edge(n, 0));

                while (!Q.empty()) {

                    current = Q.top().v;
                    Q.pop();
                    for (int i = 0; i < v[current].adj.size(); i++) {
                        edge a = v[current].adj[i];
                        if (d[a.v] > d[current] + a.weight) {
                            d[a.v] = d[current] + a.weight;
                            Q.push(edge(a.v, d[a.v]));
                        }
                    }
                }
        }
};

int main(){

    int cases;
    si(cases);

    int v, a, ini, fim;
    int v1, v2, w;
    while(cases--){
        si(v); si(a);
        si(ini); si(fim);

        graph g;

        for(int i = 1; i <= v; i++){
            g.add_v(i);
        }

        for(int i = 0; i < a; i++){
            si(v1); si(v2); si(w);
            g.add_a(v1, v2, w);
        }

        g.dijkstra(ini, v+1);
        int dist = d[fim];

        if(dist < 0 || dist >= INF) printf("NONE\n");
        else printf("%d\n", dist);

    }

}

这是最短的（超过时间限制）：

#include <bits/stdc++.h>
using namespace std;

struct edge{
    int v, w;
    edge(){}
    edge(int a, int b){v = a; w = b;}
};
bool operator < (edge a, edge b) {return a.w < b.w;}
const int INF = INT_MAX;
typedef vector<vector<edge> > graph;
typedef priority_queue<edge> heap;
int d[100020];

void Dijkstra(graph G, int length, int s){
    for(int i = 1; i <= length; i++) d[i] = INF;
    edge base;
    base.v = s;
    base.w = d[s] = 0;
    heap H;
    H.push(base);

    while(!H.empty()){
        int current = H.top().v;
        H.pop();
        for (int i = 0; i < G[current].size(); i++) {
            edge a = G[current][i];
            if (d[a.v] > d[current] + a.w) {
                d[a.v] = d[current] + a.w;
                H.push(edge (a.v, d[a.v]));
            }
        }
    }
}

int main(){
    int cases;
    int n, m, s, e;
    int v1, v2, w;

    scanf("%d", &cases);
    while(cases--){
        scanf("%d %d %d %d", &n, &m, &s, &e);
        graph G(n + 1);

        for(int i = 0; i < m; i++){
            scanf("%d %d %d", &v1, &v2, &w);
            G[v1].push_back(edge(v2, w));
            G[v2].push_back(edge(v1, w));
        }

        Dijkstra(G, n, s);

        if(d[e] != INF) printf("%d\n", d[e]);
        else printf("NONE\n");
    }
}

Answer 1

STL 的容器很慢。必要时避免使用向量。

这是我的 dij：

class graph
{
public :
    int head[N],next[M],node[M];
    int dist[M];
    int tot;
    void init()
    {
        tot = 0;
        CLR(head,-1);
    }
    void add(int x,int y,int z = 1)
    {
        node[tot] = y;
        dist[tot] = z;
        next[tot] = head[x];
        head[x] = tot++;
    }
    graph() {init();}
} g;
int dist[N]; ///the distance
///src means source. ter is optional, it means terminal
void dij(int src, graph &g, int ter=-1) 
{
    memset(dist,0x3f,sizeof(dist)); ///init d[i] as a very large value
    dist[src] = 0;
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
    pq.push(make_pair(dist[src],src));
    while(!pq.empty())
    {
        int x = pq.top().second;
        int d = pq.top().first;
        if(d != dist[x])continue;
        if(x == ter)return ;
        for(int i = g.head[x] ; ~i ; i = g.next[i])
        {
            int y = g.node[i];
            if(d+g.dist[i]<dist[y])
            {
                dist[y] = d + g.dist[i];
                pq.push(make_pair(dist[y],y));
            }
        }
    }
}

Answer 2

区别在于您如何控制优先级队列。在长版本中，首先取权重较小的边，这使您能够更早地找到最优值并缩短许多可能的路径：

    bool operator < (const edge & o) const {
            return weight > o.weight;
    }

在简短版本中，您的行为（意外地？）颠倒了，始终取权重最大的边，这意味着您有效地探测了所有可能的路径。

    bool operator < (edge a, edge b) {return a.w < b.w;}

更改不等式运算符，两个版本将运行同样快。

Dijkstra 运行慢

Dijkstra running slow

algorithm

performance

graph

dijkstra

Dijkstra 运行 慢

Dijkstra running slow

algorithm

performance

graph

dijkstra

Dijkstra 运行慢