#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;

int destí, origen, vèrtexs = 0;
int * costos = NULL;

void Dijkstra (int vèrtexs, int origen, int destinació, int * costos){
 int i, v, cont = 0;
 int * ant, * tmp;
 int * z;/* vèrtexs per als quals es coneix el camí mínim */
 double min;
 double * dist = new double [vèrtexs];/* vector amb els costos de dos camins */

 /* Aloc les línies de la matriu */
 ant = new int [vèrtexs];
 tmp = new int [vèrtexs];
 z = new int [vèrtexs];

 for (i = 0; i <vèrtexs; i++){
 if (costos [(origen - 1) * vèrtexs+i] ! =- 1){
 ant [i] = origen - 1;
 ist [i] = costos [(origen-1) * vèrtexs+i];
 }
 else{
 ant [i] = -1;
 dist [i] = HUGE_VAL;
 }
 z [i] = 0;
 }
 z [origen-1] = 1;
 dist [origen-1] = 0;

 /* Bucle principal */
 do{

 /* Trobant el vèrtex que ha d'entrar a z */
 min = HUGE_VAL;
 for (i = 0; i <vèrtexs; i++)
 if (! z [i])
 if (dist [i]> = 0 & & dist [i] <min){
 min = dist [i]; v = i;
 }

 /* Calculant les distàncies dels nodes veïns de z */
 if (min ! = HUGE_VAL & & v ! = destinació - 1){
 z [v] = 1;
 for (i = 0; i <vèrtexs; i++)
 if (! z [i]){
 if (costos [v * vèrtexs+i] ! = -1 & & dist [v]+costos [v * vèrtexs+i] <dist [i]){
 dist [i] = dist [v]+costos [v * vèrtexs+i];
 ant [i] = v;
 }
 }
 }

 }While (v ! = destinació - 1 & & mín ! = HUGE_VAL);

 /* Mostra el resultat de la cerca */
 cout << "\tde" <<origen << "per a" <<destí << "\t";
 if (min == HUGE_VAL){
 cout << "No Existeix\n";
 cout << "\tCost:\t-\n";
 }
 else{
 i = destí;
 i = ant [i-1];
 while (i ! = -1){
 //Printf ("<-% d ", i+1);
 tmp [cont] = i+1;
 cont++;
 i = ant [i];
 }

 for (i = cont; i> 0; i -){
 cout <<tmp [i-1] << "-->";
 }
 cout <<destinació;

 cout << "\n\tCost:" <<dist [destinació-1] << "\n";
 }

 delete (dist);
 delete (ant);
 delete (tmp);
 delete (z);
}

int menu (void){
 int opció;
 cout << "Implementació de l'Algorisme de Dijkstra\n";
 cout << "Menu:\n";
 cout << ">> 1. Crear el graf\n>> 2. Determinar el menor camí del graf\n>> 0. Sortir del programa\n";
 cout <<endl;
 cout << "Opció:";
 cin>> opció;
 while (opció <0||opcio> 2){
 cout << "Opció Invalida. Digitela novament:";
 cin>> opció;
 }
 return opció;
}

void add (void){

 do{
 cout << "\nIntrodueixi el nombre de vèrtexs (no mínim de 2):";
 cin>> vèrtexs;
 }While (vèrtexs <2);

 if (! costos)
 delete (costos);

 costos = new int [vèrtexs * vèrtexs];

 for (int i = 0; i <= vèrtexs * vèrtexs; i++)
 costos [i] = -1;

 cout << "N º Vertices =" <<vèrtexs <<endl;
 cout << "Ara unim els vèrtexs:\n";

 bool segueixo = true;

 int origen;
 int destinació;

 while (segueixo){
 cout << "Escolliu el primer vèrtex de l'aresta:" <<endl;
 do{
 cin>> origen;

 if (origen> vertices){
 cout << "El nombre del vèrtex ha de ser menor de" <<vèrtexs <<endl;
 }
 }while (origen> vertices);

 cout << "Escolliu el segon vèrtex de l'aresta:" <<endl;
 do{
 cin>> destinació;

 if (destinació> vertices){
 cout << "El nombre de vèrtex ha de ser menor de" <<vèrtexs <<endl;
 }
 }while (destinació> vertices);

 int pes = 0;
 cout << "Pes:" <<endl;
 cin>> pes;

 costos [(origen-1) * vèrtexs+destinació - 1] = pes;
 costos [(destinació-1) * vèrtexs+origen - 1] = pes;


 int seguir = 1;
 cout << "Voleu afegir una altra aresta? (0 - NO, 1 - SI, per defecte 1):";
 cin>> seguir;
 segueixo = (seguir == 1);
 }
}

void cercar (void){
 int i, j;

 cout << "Llista dels Menors Camins a Graf Atès:\n";

 for (i = 1; i <= vèrtexs; i++){
 for (j = 1; j <= vèrtexs; j++)
 Dijkstra (vèrtexs, i, j, costos);
 cout <<endl;
 }

 cout << "<Premeu ENTER per tornar al menú principal.\n";
}

int main (int argc, char ** argv){
 int opció;

 do{
 opcion = menu ();
 switch (opció){
 case 1:
 add ();
 break;
 case 2:
 cercar ();
 break;
 }

 }While (opció ! = 0);
 delete (costos);

 cout << "\nFins la proxima ...\n\n";
 system ("pause");

 return 0;
}

struct T_Heap{
 A turo;
 int num_elem;
};

void CrearHeap (T_Heap & heap){
 heap.num_elem = 0;
 for (int i = 0; i <MAX_HEAP; i++){
 heap.monticulo [i] = NULL;
 }
}

void Intercanviar (T_Heap & heap, int i, int j){
 T_Lista aux;

 aux = heap.monticulo [i];
 heap.monticulo [i] = heap.monticulo [j];
 heap.monticulo [j] = aux;
}

void Meter (T_Heap & heap, const T_Lista & elem){
 int k;

 k = heap.num_elem;
 heap.monticulo [k] = elem;
 while (k ! = 0||(heap.monticulo [k] --> pes> heap.monticulo [((k-1)/2)] --> pes){
 Intercanviar (heap, k, ((k-1)/2));
 k = (k-1)/2;
 }
 heap.num_elem++;
}

void Treure (T_Heap & heap, int & elem){
 int k;

 elem = heap.monticulo [0];
 heap.monticulo [0] = heap.monticulo [heap.num_elem-1];
 heap.monticulo [heap.num_elem-1] = NULL;
 heap.num_elem--;
 k = 0;
 while (k <heap.num_elem && (heap.monticulo[k]--> pes <heap.monticulo [2 * k+1] --> pes||
 heap.monticulo [k] --> pes <heap.monticulo [2 * k+2] --> pes)){
 if (heap.monticulo [k] <heap.monticulo [2 * k+1]){
 Intercanviar (heap, k, 2 * k+1);
 k = 2 * k+1;
 }else{
 Intercanviar (heap, k, 2 * k+2);
 k = 2 * k+2;
 }
 }
}

bool HeapLleno (const T_Heap & heap){
 return (heap.num_elem == MAX_HEAP);
}

bool HeapVacio (const T_Heap & heap){
 return (heap.num_elem == 0);
}

void DestruirHeap (T_Heap & heap){
 for (int i = 0; i <MAX_HEAP; i++){
 heap.monticulo [i] = NULL;
 }
 heap.num_elem = 0;
}

void Dijkstra (const T_Grafo & graf, int origen, T_Vector & distàncies, T_Vector & anteriors)
{
 T_Vector marcats;
 T_Heap colap;
 T_Lista aux;

 InicializarVector (distàncies);//inicialitza els elements a -1
 InicializarVector (anteriors);
 InicializarVector (marcats);
 distàncies [origen] = 0;
 marcats [origen] = 0;
 CrearHeap (colap);
 MeterAdyacentes (colap, graf, origen, marcats);
 while (! HeapVacio (colap){
 aux = Treure (colap);
 marcats [aux--> origen] = 0;
 MeterAdyacentes (colap, graf, aux--> origen, marcats);
 while (aux ! = NULL){
 if (distàncies [aux--> destí]> (distàncies [aux--> origen]+aux--> pes)){
 distàncies [aux--> destí] = distàncies [aux--> origen]+aux--> pes;
 pare [aux--> destí] = aux--> origen;
 }
 aux = aux--> seg;
 }
 }
}