There is an alternative way of implementing Dijkstra’s algorithm that avoids use

Question

There is an alternative way of implementing Dijkstra’s algorithm that avoids use of the locator pattern but increases the space used for the priority queue, Q, from O(n) to O(m) for a weighted graph, G, with n vertices and m edges. The main 14.6. Exercises 419 idea of this approach is simply to insert a new key-value pair, (D[v], v), each time the D[v] value for a vertex, v, changes, without ever removing the old key-value pair for v. This approach still works, even with multiple copies of each vertex being stored in Q, since the first copy of a vertex that is removed from Q is the copy with the smallest key. Describe the other changes that would be needed to the description of Dijsktra’s algorithm for this approach to work. Also, what is the running time of Dijkstra’s algorithm in this approach if we implement the priority queue, Q, with a heap?

Explanation / Answer

class Graph
{
public:
vector<int> nodes ;
vector<vector<pair<int,int> > > edges ;
void addNode()
{
nodes.push_back(nodes.size()) ;
vector<pair<int,int> > temp ; edges.push_back(temp);
}
void addEdge(int n1, int n2, int w)
{
edges[n1].push_back(make_pair(n2,w)) ;
}
pair<vector<int>, vector<int> > shortest(int source)
{
vector<int> dist(nodes.size()) ;
fill(dist.begin(), dist.end(), INF) ; dist[source] = 0 ;
vector<int> pred(nodes.size()) ;
fill(pred.begin(), pred.end(), -1) ;
for(int i=0; i<(int)edges[source].size(); i++)
{
dist[edges[source][i].first] = edges[source][i].second ;
pred[edges[source][i].first] = source ;
}
set<pair<int,int> > pq ;
for(int i=0; i<(int)nodes.size(); i++)
pq.insert(make_pair(dist[i],i)) ;
while(!pq.empty())
{
pair<int,int> item = *pq.begin() ;
pq.erase(pq.begin()) ;
int v = item.second ;
for(int i=0; i<(int)edges[v].size(); i++)
{
if(dist[edges[v][i].first] > dist[v] + edges[v][i].second)
{
pq.erase(std::find(pq.begin(), pq.end(),make_pair(dist[edges[v][i].first],edges[v][i].first))) ;
pq.insert(make_pair(dist[v] + edges[v][i].second,edges[v][i].first)) ;
dist[edges[v][i].first] = dist[v] + edges[v][i].second ;
pred[i] = edges[v][i].first ;
}
}
}
return make_pair(dist,pred) ;
}
pair<vector<int>, vector<int> > shortestwpq(int source)
{
vector<int> dist(nodes.size()) ;
fill(dist.begin(), dist.end(), INF) ; dist[source] = 0 ;
vector<int> pred(nodes.size()) ;
fill(pred.begin(), pred.end(), -1) ;
for(int i=0; i<(int)edges[source].size(); i++)
{
dist[edges[source][i].first] = edges[source][i].second ;
pred[edges[source][i].first] = source ;
}
vector<pair<int,int> > pq ;
for(int i=0; i<(int)nodes.size(); i++)
pq.push_back(make_pair(dist[i],i)) ;
while(!pq.empty())
{
pair<int,int> item = *pq.begin() ;
pq.erase(pq.begin()) ;
int v = item.second ;
for(int i=0; i<(int)edges[v].size(); i++)
{
if(dist[edges[v][i].first] > dist[v] + edges[v][i].second)
{
dist[edges[v][i].first] = dist[v] + edges[v][i].second ;
pred[i] = edges[v][i].first ;
}
}
}
return make_pair(dist,pred) ;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.