#include "stdafx.h"
#include "Graph.h"
#include "QueuePrior.h"

//----------------------------------------------------------------------------
double Dijkstra(Vertex* Village, int nSize, int nFirst)
{
    PQueue* q = PQInit(nSize);           //pusta kolejka prior
    double* Pathlen = (double*)calloc(nSize, sizeof(double));       //tablica na wierzcholki grafu
	int** Path = NULL;												//tablica ścieżek
	int **wsk = Path = (int**)(calloc(nSize,sizeof(int*)));			//Ścieżki do wierzchołków
	if (!Pathlen || !Path )
    {
        perror("Error creating, no memory!!");
        return 10;
    }

	for( int i = 0; i<nSize; i++, wsk++)							//Wzięte z CreateMatrix
	{
		*wsk = (int*)(calloc(nSize,sizeof(int)));
		if(! (*wsk) ) return 10;
	}

	for (int z = 0; z<nSize;z++)									//Uzupełniam -1
		for(int x = 0; x<nSize; x++)
			Path[z][x] = -1;

	for (int i = 0; i < nSize; i++)
		Pathlen[i] = INT_MAX;

	PQEnQueue(q, nFirst, 0);//klucz nFirst a prior 0
	Pathlen[nFirst] = 0;      // odleglosc do siebie samego = 0 !!

	Path[nFirst][0] = nFirst;											//Przypisuje pierwszy wierzchołek do drogi

	while (!(PQisEmpty(q)))
	{
		int k = PQDeQueue(q);

		if (Village[k].Type)// jesli sklep
		{
			Village[nFirst].NearestShop = k;// zapamietuje indeks do najblizszego sklepu
			Village[nFirst].WayToShop = Pathlen[k];
			Village[nFirst].TimeAll = Village[nFirst].WayToShop / SPEED;
			Village[nFirst].WhichVertex = Path[k];

			PQRelease(q);

			return Pathlen[k];      //zwraca droge do sklepu
		}

		else //to kolejny obieg
			for (NItem* j = Village[k].nList; j; j = j->pNext)
			{
				int Node = j->nKey;

				if (Pathlen[k] + j->length < Pathlen[Node])
				{
					Pathlen[Node] = Pathlen[k] + j->length;

					for( int chuj = 0; chuj < nSize; chuj++)
						Path[Node][chuj] = Path[k][chuj];			//Przepisz drogę do dotychczasowego wierzchołka

					int l = 0;
					while ( Path[Node][l] != -1 )
						l++;

					Path[Node][l] = Node;					//Dopisz wierzchołek na koniec ścieżki

					PQEnQueue(q, Node, Pathlen[Node]);
				}
			}
	}
	return 0;
}
//---------------------------------------------------------------------------
void DFS(Vertex* Village, int st, int* tabVisited)
{
	tabVisited[st] = 1;
	NItem* v = Village[st].nList;
	while( v )
	{
		v->time = v->length / SPEED;

		if ( !tabVisited[v->nKey] )
			DFS(Village, v->nKey, tabVisited);

		v = v->pNext;
	}
}