首页 > 试题广场 >

下面的程序实现了,使用优先队列的dijkstra算法求解起点

[问答题]

下面的程序实现了,使用优先队列的dijkstra算法求解起点为0的单源最短路问题。有定义如下:

typedef pair<int, int> pii;

priority_queue<pii, vector<pii>, greater<pii> > q;

pair在比较时会先比较第一个数,再比较第二个数,因此q是一个小元素优先的优先队列。对于图中节点x,first[x]代表其第一条出边的编号。对于图中编号为e的边,v[e]代表这条边的终点,w[e]代表这条边的权值。

试完善以下代码:

bool done[MAXN];

for (int i = 0; i < n; i++) d[i] = (i == 0 ? 0 : INF);

memset(done, false, sizeof(done));

q.push(make_pair(d[0], 0));

while(!q.empty()) {

        pii u = q.top(); q.pop();

        int x = u.second;

        if (done[x])              ;

        done[x] = true;

        for (int e = first[x]; e != -1; e = next[e])

          if (                       ) {

             d[v[e]] =                
                          ;

          }

}

continue;
d[x]+w[e]<d[v[e]];
d[v[e]]=d[x]+w[e]
q.push(make_pair(d[v[e]],v[e]));
编辑于 2021-09-21 20:46:43 回复(0)