#include <stdio.h>
#define KNOTENZAHL 7
#define MAXABST 20
#define UNENDLICH (MAXABST*(KNOTENZAHL-1)+1)


void InitialisiereAlles(short AA[KNOTENZAHL][KNOTENZAHL], short  WW[KNOTENZAHL][KNOTENZAHL], short  DD[KNOTENZAHL], short VV[KNOTENZAHL], short SoS[KNOTENZAHL], short QQ[KNOTENZAHL])
{
	short i=0,j=0; 
	for(i=0;i<KNOTENZAHL;i++)
	{
		DD[i]=UNENDLICH;
		VV[i]=-1;
		SoS[i]=0;
		QQ[i]=1;
		for(j=0;j<KNOTENZAHL;j++)
		{
			AA[i][j]=0; 
			WW[i][j]=UNENDLICH;
		}
	}
	return;  
}

/*----------------------------------------------------*/
  
void InitialisiereRest(short  DD[KNOTENZAHL], short VV[KNOTENZAHL], short SoS[KNOTENZAHL], short QQ[KNOTENZAHL])/* Hier bleiben die Adjazenz- und Gewichtsmatrix unveraendert*/
{
	short i=0; 
	for(i=0;i<KNOTENZAHL;i++)
	{
		DD[i]=UNENDLICH;
		VV[i]=-1; 
		SoS[i]=0;
		QQ[i]=1;
	}
	return;  
}  

/*----------------------------------------------------*/

void EingabeA(short AA[KNOTENZAHL][KNOTENZAHL], short  WW[KNOTENZAHL][KNOTENZAHL])
{
	short i=0,j=0, maxab=MAXABST; 
	for(i=0;i<KNOTENZAHL;i++)
	{
		for(j=0;j<KNOTENZAHL;j++)
		{
			if(i!=j)
			{
				printf("Falls es eine Kante vom Knoten %hi zum Knoten %hi gibt, geben Sie bitte 1 ein, sonst 0: ",(i+1),(j+1));
				scanf("%hi",&AA[i][j]);
				while(AA[i][j]!=0 && AA[i][j]!=1)
				{
					printf("Noch einmal ordentlich: ");
					scanf("%hi",&AA[i][j]); 
				}
			   
				if(AA[i][j]==1)    
				{
					printf("Geben Sie nun das Gewicht der Kanten vom Knoten %hi zum Knoten %hi ein; zulässig sind Zahlen zwischen 0 und %hi: ",(i+1),(j+1),maxab);
					scanf("%hi",&WW[i][j]);
					while(WW[i][j]<0 || WW[i][j]>maxab )
					{
						printf("Unzulässiger Wert. Noch einmal bitte: ");
						scanf("%hi",&WW[i][j]); 
					}
			      
				}
			    
			}
		}
	} 
	return;
}
  
 
/*----------------------------------------------------*/
 
void KontrollausgabeA(short AA[KNOTENZAHL][KNOTENZAHL], short  WW[KNOTENZAHL][KNOTENZAHL])
{
	short i=0,j=0; 
	for(i=0;i<KNOTENZAHL;i++)
	{
		for(j=0;j<KNOTENZAHL;j++)
		{
			if(i!=j)
			{
				printf("Kante vom Knoten %hi zum Knoten %hi:  %hi.",(i+1),(j+1),AA[i][j]);
				if(AA[i][j]==1)
					printf("Gewicht: %hi.\n",WW[i][j]);
				else
					printf("\n");
			}
		}
	} 
	return;
} 


/*----------------------------------------------------*/
  
short ExtractMinQ(short QQ[KNOTENZAHL], short  DD[KNOTENZAHL])
{
	short suchknot=-1, abstand=UNENDLICH, ell=0;
	for(ell=0;ell<KNOTENZAHL;ell++)
	{
		if(QQ[ell]==1 && DD[ell]<=abstand) 
		{
			suchknot=ell;
			abstand=DD[ell];
		}
	      
	}
	return(suchknot);
}
    
    
 
/*----------------------------------------------------*/   
  
void AusgabeSuchergebnis(short sk, short  DD[KNOTENZAHL], short VV[KNOTENZAHL])
{
	short i=0,dd=0,vv=0;
	printf("Startknoten:  %hi.\n",(sk+1));
	for(i=0;i<KNOTENZAHL;i++)
	{
		if(i!=sk)
		{
			printf("Knoten %hi: ",(i+1)); 
			if(VV[i]==-1)
				printf("unerreichbar.\n");
			else  
			{
				printf("Abstand zum Startknoten: %hi; Vorgänger: %hi",DD[i],(VV[i]+1));
				dd=DD[i];
				vv=VV[i];
				while(vv!=sk)
				{
					vv=VV[vv];
					printf(", %hi",(vv+1));
				}
				printf(". \n");	 
			}
		}
	}
	return;    
}


/*----------------------------------------------------*/

int main(void)
{
  
	short s=0, knz=KNOTENZAHL;
	short A[KNOTENZAHL][KNOTENZAHL], W[KNOTENZAHL][KNOTENZAHL], D[KNOTENZAHL],V[KNOTENZAHL],S[KNOTENZAHL],Q[KNOTENZAHL];
	short u=0,v=0,frage=1, SZ=0, QZ=knz;
  
	InitialisiereAlles(A,W,D,V,S,Q);
	EingabeA(A,W); 
	KontrollausgabeA(A,W);
  
	while(frage==1)
	{
		InitialisiereRest(D,V,S,Q);  
		SZ=0;
		QZ=knz;
    
		printf("Von welchem Startknoten aus sollen wir suchen?\n        Geben Sie eine Zahl zwischen 1 und %hi ein: ",knz);
		scanf("%hi",&s);
	 
		while(s<1 || s>knz)
		{
			printf("Noch einmal ordentlich: ");
			scanf("%hi",&s); 
		}
	
		s=s-1;
		D[s]=0;
		V[s]=-1;
  
		while(QZ>0)
		{
			u=ExtractMinQ(Q,D);
			//printf("Arbeitsknoten: %hi.\n", u);
			S[u]=1;
			SZ=SZ+1;
			Q[u]=0;
			QZ=QZ-1;
			for(v=0;v<knz;v++)
			{
				if(A[u][v]==1)
				{
					if((D[u]+W[u][v])<D[v])
					{
						D[v]=D[u]+W[u][v];
						V[v]=u;
					}
				}
			}
	   
		}
	
 
  
		AusgabeSuchergebnis(s,D,V);
    
		printf("Möchten Sie denselben Graphen von einem anderen Startknoten aus durchsuchen?\n In diesem Falle geben Sie nun eine 1 ein.\n Möchten Sie das Programm beenden, geben Sie eine 0 ein. \n Ihr Wunsch: ");
		scanf("%hi",&frage); 
  
	}
	return(0);
}