Dijkstra with unordered_map instead of array

dijkstra_pq_umap.cpp

#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <queue>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <string>

using namespace std;

typedef unordered_map<string,int> umap_str_int;

int LIMIT = 1e5;

struct Node{
  int id;
  int co;
  bool ck;
};

class Compare {
  public:
    bool operator() (Node* a, Node* b){
      return a->co > b->co;
    }
};

inline string key(int i, int j){
  return to_string(i)+"_"+to_string(j);
}

void ___showedge(umap_str_int edges,int nodenum){
  for(int i = 0; i < nodenum; ++i){
    for(int j = 0; j < nodenum; ++j){
      if(edges.find(key(i,j)) == edges.end()) cout << "---" << " ";
      else cout << setw(3) << edges[key(i,j)] << " "; 
    }
    cout << endl;
  }
  cout << endl;
}

void ___shownodes(Node* nodes, int nodenum){
  for(int i = 0; i < nodenum; ++i)
    cout << nodes[i].id << ":" << nodes[i].co << " " << nodes[i].ck << endl;
  cout << endl;
}

void showpath(int* path, int nodenum, Node* nodes){
  vector<int> rev;
  int node = nodenum-1;
  while(true){
     rev.push_back(node);
     node = path[node];
     if(node==0) break;
  }
  rev.push_back(0);
  reverse(rev.begin(),rev.end());
  for(auto &p: rev)
     cout << p << "(" << nodes[p].co << ") -> ";
  cout << "GOAL!!" << endl;
}

void dijkstra(umap_str_int edges,int nodenum){
  Node* nodes = new Node[nodenum];
  for(int i = 0; i < nodenum; ++i){
    nodes[i].id = i;
    nodes[i].co = LIMIT;
    nodes[i].ck = false;
  }

  priority_queue<Node*,vector<Node*>,Compare> pq;
  nodes[0].co = 0;
  pq.push(&nodes[0]);

  Node* node;
  int* path = new int[nodenum];
  while(0<pq.size()){
    //___shownodes(nodes,nodenum);
    node = pq.top(); pq.pop();
    node->ck = true;
    if(node->id == nodenum-1) break;
    for(int i = 0; i < nodenum; ++i){
      if(nodes[i].ck) continue;
      if(edges.find(key(node->id,i))==edges.end()) continue;
      if(node->co+edges[key(node->id,i)] < nodes[i].co){
        nodes[i].co = node->co+edges[key(node->id,i)];
        path[i] = node->id;
        pq.push(&nodes[i]);
      }
    }
  }
  //___shownodes(nodes,nodenum);
  showpath(path,nodenum,nodes);
}

int main(){
  int nodenum;
  int nodenum1;
  int edgenum=0;
  cout << "# of nodes: ";
  cin >> nodenum;
  cout << "# of edges: ";
  while(edgenum < nodenum-1 || nodenum*nodenum < edgenum)
    cin >> edgenum;
  cout << endl;

  umap_str_int edges;

  for(int i = 0; i < nodenum-1; ++i)
    edges[key(i,i+1)] = 1000-1;

  int fr,to,co;
  for(int i=0;i<edgenum-(nodenum-1);i++){
    while(true){
      fr=rand()%nodenum;
      to=rand()%nodenum;
      co=rand()%1000;
      if(edges.find(key(fr,to))==edges.end()){
        edges[key(fr,to)]=co;
        break;
      }
    }
  }
  //___showedge(edges,nodenum);

  dijkstra(edges,nodenum);

  return 0;
}

$ time ./dijkstra_pq_umap 
# of nodes: 1000
# of edges: 5000

0(0) -> 957(260) -> 95(481) -> 72(647) -> 149(839) -> 937(1460) -> 55(1951) -> 999(2208) -> GOAL!!
./dijkstra_pq_umap  0.24s user 0.01s system 7% cpu 3.405 total

$ time ./dijkstra_pq_umap
# of nodes: 100000
# of edges: 500000

0(0) -> 35470(183) -> 84610(640) -> 6968(765) -> 78268(1015) -> 98802(1099) -> 94498(1255) -> 63553(1256) -> 13496(1322) -> 90236(1714) -> 47330(2293) -> 27809(2523) -> 99999(2890) -> GOAL!!
./dijkstra_pq_umap  2773.30s user 0.06s system 99% cpu 46:17.30 total