Dijkstra Algorithm for finding shortest path to all vertices from a single source.

dijkstra_algorithm.cpp

//Algoritmo de Dijkstra, el Camino mas Corto
//Fork de Dijkstra por: nateshmbhat https://gist.github.com/nateshmbhat/1a79daa00a148e44ad79c3e338977440
//Fork de nateshmbhat por: Alejandro Sacristan Leal https://gist.github.com/AtonCode/acd3077fa70a2cbb6fcbe211a206c4dd
//

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string>

using namespace std ;

//Grafo G en su forma matricial
int cost [7][7] =
{{0,14,999,999,10,17,999},
 {14,0,9,10,3,999,999},
 {999,9,0,2,999,999,999},
 {999,10,2,0,999,999,7},
 {10,3,999,999,0,6,4},
 {17,999,999,999,6,0,1},
 {999,999,999,7,4,1,0}}, n=7; 

//Calcula y guarda la distancia minima y el nodo visitado, Se actualiza en cada iteracion
int getMin(int dist[] , bool visitedNodos[]){

    int nodo = 0 ; 
    int min = INT_MAX ; 
    for(int i=0;i < n ; i++){
        if(!visitedNodos[i] && dist[i]<min){
            min = dist[i] ; 
            nodo = i ; 
        }
    }
    
    return nodo ; 
}

// Permite visualizar el resultado del algoritmo para el camino mas corto
void display(int dist[] , int parNodos[] ){

   for(int i =0 ;i < n ;i++){
       int temp = parNodos[i] ; 
       cout<<i << " <- " ;

       while(temp!=-1)
       {
           cout<< temp << " <- " ;
           temp = parNodos[temp] ; 
       }
       cout<<endl; 
       cout<<"::::Distance = " << dist[i]<<endl;
       cout<<" "<<endl;
        
   } 
}

// Algortimo Principal
void dijkstra(int src ){

    int par[10] , dist[10] ; 
    bool visited[8] ={0} ; 
    fill(dist , dist+n  , INT_MAX ) ; 

    dist[src] = 0 ; 
    par[src] = -1 ;
    
    cout<<"Nodos ordenados de menor distancia a Nodo 0/A: "<<endl;
    cout<<" "<<endl;
    for(int g = 0  ;g < n-1 ; g++){

        int u = getMin(dist ,visited); 
        
        visited[u] = true;
        cout<< "Nodo = " << u <<endl; 
        for(int v =0 ; v< n ;v++){
            if(!visited[v] && (dist[u]+cost[u][v]) <  dist[v] && cost[u][v]!=9999){
                par[v] = u ; 
                dist[v] = dist[u] + cost[u][v] ; 
            }
        }
    }

    cout<<" "<<endl;
    cout<<"Rutas y Distancias:"<<endl;
    display(dist , par); 
}



int main(void) {

    cout<<" "<<endl;
    cout<<"Algoritmo de Dijkstra, el camino mas corto "<<endl;
    cout<<"Fork de Dijkstra por: nateshmbhat"<<endl;
    cout<<"Fork de nateshmbhat por: Alejandro Sacristan Leal"<<endl;
    cout<<" "<<endl;
    cout<<"Reprecentacion del Grafo G en Matrix"<<endl;
    cout<<" "<<endl;

    //Dibujando Matriz de Grafo G
    for(int i = 0;i < 7; i++){
        for(int j = 0;j < 7;j++){
            cout<< cost[i][j] <<"\t";
        }
        cout<<" "<<endl;
    }
    cout<<" "<<endl;

    dijkstra(0) ; 
}