#include <stdio.h>
#include <stdlib.h>
#include "variables.h"

//Funcion dijkstra	: Calcula la ruta mas corta entre un origen y un destino de elementos de un grafo representado 
//			  por su matriz de adyacencias
//Variables de entrada  : La matriz de adyacencias, el vertice de origen, el de destino y el numero de vertices en el grafo
//Valor devuelto        : Vector de distancias rutas.
//Precondiciones        : El grafo se considera NO dirigido
Ruta_DistT OSPFdijkstra (MatrizT Matriz, int origen, int destino, int N_Vertices)
{
  int* visitados;       //Vector que contiene el estado de visita de los vertices
  Ruta_DistT Ruta_Dist; //Vector con informacion de rutas y distancias entre el nodo de origen y el resto
  int i,                //Contador
      min,              //Vertice mas cercano al origen (durante analisis del grafo)
      actual;           //Vertice siendo procesado en un instante dado.
  float temp;           //Variable para guardar datos temporales.

  visitados = malloc (N_Vertices*sizeof(int));  //Crear espacio en memoria para el vector "visitados"
  Ruta_Dist = malloc (N_Vertices*sizeof(RDE));  //Crear espacio para vector de rutas y distancias.

  //Inicializacion...
  for (i = 0; i < N_Vertices; i++)
    {
      if (Matriz[origen][i] != -1)              //Si el vertice i esta conectado al origen...
        {                                       //...entonces guardamos la info en el vector de rutas
          Ruta_Dist[i].ruta = origen;
          Ruta_Dist[i].dist = Matriz[origen][i];
        }//EndIf
       else                                     //sino....
         {                                      //...lo declaramos como momentaneamente inalcanzable.
           Ruta_Dist[i].ruta = -1;
           Ruta_Dist[i].dist = INFINITO;
         }//EndElse
      visitados[i] = 0;                         //Resetear el vector "visitados" para indicar que aun no se inicia el algoritmo
    }//EndFor
  visitados[origen] = 1;                        //origen es el punto de partida. No hay que volver a el
  actual = origen;                              //Establecer vertice a analiazar en el origen

  do
    {
        min = origen;
        for (i = 0; i < N_Vertices; i++) //En esta parte, buscamos la distancia mas corta entre el origen y todos los vertices ya explorados
          {
            if ((Ruta_Dist[i].dist < Ruta_Dist[min].dist) && (visitados[i] == 0))
              {
                min = i;                //Si se descubre un nuevo minimo, entonces hay que mantener su posicion...
              }//EndIf
          }//EndFor
        Matriz[actual][min] = -1;       //Elimiar el nuevo minimo de la matriz de adyacencias...
        Matriz[min][actual] = -1;       //...y su traspuesto
        visitados[min] = 1;	//Establecer el nuevo minimo como ya visitado. Esto indica que la distancia actual al origen es minima.
        actual = min;
        for (i = 0; i < N_Vertices; i++)
          {
            if ((Matriz[actual][i] != -1)&&(visitados[i]==0)&&((temp = Ruta_Dist[actual].dist+Matriz[actual][i])<Ruta_Dist[i].dist))
              {
                Ruta_Dist[i].ruta = actual;	//Si el vertice analizado es no mínimo, y, además, la nueva ruta posible tiene una
                Ruta_Dist[i].dist = temp;	//métrica menor que la actual, entonces guardamos la nueva ruta y métrica.
              }//EndIf
          }//EndFor
    }
  while (visitados[destino] == 0);		//Iterar hasta que la ruta al destino sea mínima.

  return (Ruta_Dist);				//Devolver vector de rutas y métricas.
}//EndOSPFdijkstra