Dijkstra

 #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <string>
    #include <list>
    #include <limits> // para numeric_limits
    #include <utility> // para pair
    #include <queue> // para priority_queue
    #include <iterator>
    #include <fstream>
    #include <cstdlib>
    #include <map>
    #include <math.h>
//  #include <CPUTimer.cpp>
    using namespace std;
    #define MAX 99999999999

    typedef vector<vector<pair<int,int> > > Grafo;
    typedef map<int, int> VerticesPorGrau;
    Grafo G;
    VerticesPorGrau mapaVerticesPorGrau;
    vector<int> caminho;
    vector<int> minDist;
    vector<int> predecessor;

    void ler_arquivo(Grafo &g);
    int contar_arestas(string nome_arquivo);
    void gravar_matriz_adjacencia(Grafo &g);
    void gravar_grau_vertices(Grafo &g);
    void dijkstra(int &fonte, int &destino);
    int contar_vertices(Grafo &g);
    void calcular_vertices_por_grau(Grafo &g, VerticesPorGrau &m);
    int main(int argc, char** argv)
    {
    //  cout << "INFORME O NOME DO ARQUIVO QUE CONTEM O GRAFO (Exemplo: \"USA-road-d.NY.gr\") E TECLE ENTER \n" << endl;
        string nome_arquivo;
      //  cin >> nome_arquivo;
        nome_arquivo = "USA-road-d.NY.gr";
        //USA-road-d.NY.gr

        //Graph g;
        int qtde_arestas = contar_arestas(nome_arquivo);
        cout << "qtde de arestas encontradas: " << qtde_arestas << endl;
        G.resize(qtde_arestas);
        cout << "Lendo o arquivo..." << endl;
        ler_arquivo(G);
        int menu_item;
        do{
            cout << "===========DIGITE AS OPCOES SEGUINTES====================" << endl;
            cout << "1 - PARA SALVAR A MATRIZ DE ADJACENCIA EM FORMATO CSV" << endl;
            cout << "2 - PARA SALVAR O GRAU DE CADA VERTICE EM CSV" << endl;
            cout << "3 - EXECUTAR O DIJKSTRA K VEZES" << endl;
            cout << "4 - DADOS SOBRE O GRAFO" << endl;
            cout << "5 - QUANTIDADE DE VERTICES POR GRAU" << endl;
            cout << "6 - PARA EXECUTAR O DIJKSTRA ESCOLHENDO ORIGEM E DESTINO" << endl;
            cout << "9 - PARA SAIR" << endl;

            cin >> menu_item;

            switch(menu_item){
             case 1  : gravar_matriz_adjacencia(G);
               break;
             case 2  : gravar_grau_vertices(G);
               break;
           case 3 :{
                 cout << "Informe o valor do K" << endl;
                 int k;
                 cin >> k;

                //para percorrer até o último vertice
                int quantidade_vertices =  contar_vertices(G);
                //int quantidade_vertices =  100000;

                for(int i = 1 ;i <= G.size(); i++) {
                  int x = G[i].size();
                  int vezes = 0;
                  if(x == 1){
                    minDist.resize(G.size());
                    predecessor.resize(G.size());
                    cout << "Executando o dijkstra do nó  " << i << " para o nó " << quantidade_vertices <<  endl;
                    dijkstra(i,quantidade_vertices);
                    cout << "FIM EXECUCAO" << endl;

                    cout << "Caminho mais curto para o nó " << i << "...." << endl;
                    for(int i=caminho.size()-1;i>=0;i--)
                      cout<<caminho[i]<<"->";
                    cout << "---------------------" << endl;

                    vezes++;
                    if (vezes >= k)
                        break;
                  }
                }
             };
               break;
             case 4  : {
                 int v =  contar_vertices(G);
                 cout << "O grafo contem :" << v << " vertices e " << qtde_arestas << " arestas. " << endl;
             }
               break;
             case 5  : {
                 calcular_vertices_por_grau(G,mapaVerticesPorGrau);
                 cout << "---------------------" << endl;
                 cout << "Grau|Qtde de Vertices|"<< endl;
                 cout << "---------------------" << endl;
                 for(int i = 1;i <= mapaVerticesPorGrau.size();i++){
                   cout <<  i << "   |" << mapaVerticesPorGrau[i] << endl;
                 }
             };
               break;
             case 6  : {
                int inicial;
                cout << "DIGITE O NO FONTE" << endl;
                cin >> inicial;
                int final;
                cout << "DIGITE O NO DESTINO" << endl;
                cin >> final;
                cout << "Executando o dijkstra..." << endl;
                minDist.resize(G.size());
                predecessor.resize(G.size());
                dijkstra(inicial,final);
                cout << "Caminho mais curto..." << endl;
                for(int i=caminho.size()-1;i>=0;i--)
                    cout<<caminho[i]<<"->";
                cout << endl;

             };break;
             default : exit(0);
            }
        }while(menu_item < 9);
        return 0;
    }
void dijkstra(int &fonte, int &destino){
    std::ofstream ofs_log_fila ("log_fila_prioridade.txt", std::ofstream::out);
           for(int i = 0 ;i < G.size(); i++) {
              predecessor[i] = -1;
              minDist[i] = MAX;
           }
           minDist[fonte] = 0;

           int tamFilaPrioridades = 0;
           priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int, int> > > Fila;
           Fila.push(make_pair(fonte,minDist[fonte]));
           tamFilaPrioridades = Fila.size();

           ofs_log_fila<<"-------------------------------------------------------------------"<<endl;
           ofs_log_fila<<"Existe "<<tamFilaPrioridades<<" elemento na fila de prioridades"<<endl;
           ofs_log_fila << "Altura do Heap Binario da fila de prioridades: 0" << endl;
           ofs_log_fila<<"-------------------------------------------------------------------"<<endl;
           int cont = 0;
           while(!Fila.empty()){
               ofs_log_fila<<++cont<<endl;

               int u = Fila.top().first;

               if(u == destino){
                ofs_log_fila<<"Encontrado o destino! Retornando..."<<endl;
                ofs_log_fila<<endl;
                   break;
               }
               Fila.pop();

               for(int i=0; i < G[u].size(); i++){
                  int v= G[u][i].first;
                  int w = G[u][i].second;

                  if(minDist[v] > minDist[u]+w){
                     minDist[v] = minDist[u]+w;
                     predecessor[v] = u;
                     Fila.push(make_pair(v,minDist[v]));
                  }
               }
               tamFilaPrioridades = Fila.size();

               if(Fila.size() == 1){
                   ofs_log_fila<<"Existe "<<tamFilaPrioridades<<" elemento na fila de prioridades"<<endl;
               }else{
                   ofs_log_fila<<"Existem "<<tamFilaPrioridades<<" elementos na fila de prioridades"<<endl;
               }

               if(tamFilaPrioridades != 0){
                   ofs_log_fila << "Altura do Heap Binario da fila de prioridades:" << floor(log2(tamFilaPrioridades)) << endl;
               }else{
                   ofs_log_fila << "Altura do Heap Binario da fila de prioridades: 0" << endl;
               }
               ofs_log_fila<<"-------------------------------------------------------------------"<<endl;
           }

           caminho.clear();
           int p = destino;
           caminho.push_back(destino);

           while(p!=fonte){
             p = predecessor[p];
             caminho.push_back(p);
           }
           ofs_log_fila.close();
    }

    void gravar_matriz_adjacencia(Grafo &g){
        cout << "Gravando a matriz de adjacencia" << endl;
        std::ofstream ofsm ("matriz_adjacencia.csv", std::ofstream::out);
        for(int i = 1 ;i <= G.size(); i++) {
            ofsm << i << ";";
            for(int j = 0; j < G[i].size(); j++){
                if(G[i].size() != 0)
                   ofsm  << G[i][j].first << ";";
              }
            ofsm << "\n";
        }
        ofsm.close();
        cout << "Terminou de gravar a matriz de adjacência" << endl;
    }
    void gravar_grau_vertices(Grafo &g){
        //mostrar os graus de cada vérticie
        cout << "Gravando o grau dos vértices" << endl;
        std::ofstream ofs ("graus_verticies.csv", std::ofstream::out);
        ofs << "Vertice;Grau\n";
        for(int i = 1 ;i <= G.size(); i++) {
            if(G[i].size() != 0)
              ofs << i << ";"<<  G[i].size() << "\n";
        }
        ofs.close();
        cout << "Terminou de gravar o grau dos vertices" << endl;

    }
    int contar_vertices(Grafo &g){
        int v = 0;
        for(int i = 1 ;i <= G.size(); i++) {
            if(G[i].size() != 0)
              v++;
        }
        return v;
    }
    void ler_arquivo(Grafo &g){
        ifstream infile;
        infile.open("USA-road-d.NY.gr");

        if (infile.is_open() && infile.good()){
            string linha;

            while(!infile.fail())
            {
                getline(infile, linha);

                if (linha.substr(0,1).compare("a") == 0){
                    //pega o nó origem do grafo
                    int posicao = linha.find_first_of(" ") + 1;
                    string substr1 = linha.substr(posicao);
                    int posicao_final = substr1.find_first_of(" ");
                    string coluna1 = substr1.substr(0,posicao_final);
                    //pega o nó destino do grafo
                    posicao = substr1.find_first_of(" ") + 1;
                    substr1 = substr1.substr(posicao);
                    posicao_final = substr1.find_first_of(" ");
                    string coluna2 = substr1.substr(0,posicao_final);

                    //pega o peso do grafo
                    posicao = substr1.find_first_of(" ") + 1;
                    substr1 = substr1.substr(posicao);
                    posicao_final = substr1.find_first_of(" ");
                    string coluna3 = substr1.substr(0,posicao_final);

                    //converte os valores para inteiro e passa para a lista de adjacências
                    int x = atoi(coluna1.c_str());
                    int y = atoi(coluna2.c_str());
                    int z = atoi(coluna3.c_str());

                    g[x].push_back(make_pair(y,z));

                }
           }
        }
        G = g;
    }
int contar_arestas(string nome_arquivo){
        ifstream infile;
        infile.open(nome_arquivo.c_str());
        int i = 0;
        if (infile.is_open() && infile.good()){
            string linha;

            while(!infile.fail())
            {
                getline(infile, linha);

                if (linha.substr(0,1).compare("a") == 0){
                  i++;
                }
           }
        }
        return i;
}
void calcular_vertices_por_grau(Grafo &g, VerticesPorGrau &m){
    for(int i = 1 ;i <= G.size(); i++) {
        int x = G[i].size();
        if(x != 0){
            x = m[x] = m[x] + 1;

         }
    }

}