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


void InitialisiereAlles(short AA[KNOTENZAHL][KNOTENZAHL],short  WW[KNOTENZAHL][KNOTENZAHL],short  DD[KNOTENZAHL],short VV[KNOTENZAHL])
{
	short i=0, j=0; 
	for(i=0;i<KNOTENZAHL;i++)
	{
		DD[i]=UNENDLICH;
		VV[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])/* Hier bleiben die Adjazenz- und Gewichtsmatrix unveraendert*/
{
	short i=0; 
	for(i=0;i<KNOTENZAHL;i++)
	{
		DD[i]=UNENDLICH;
		VV[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 %hi und %hi: ",(i+1),(j+1),((-1)*maxab), maxab);
					scanf("%hi",&WW[i][j]);
					while(WW[i][j]<((-1)*maxab) || 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;
} 
  
 /*-----------------------------------------*/ 
  
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];
	short u=0,v=0,i=0,frage=1,ausgeber=1;
  
	InitialisiereAlles(A,W,D,V);
  
    
	printf("Dieses Programm findet kuerzeste Pfade in einem gewichteten gerichteten Graphen mit den Knoten 1,2,...%hi durch.\n\
Zunaechst geben Sie bitte die Adjazenzmatrix und ggfs. die entsprechenden ganzzahligen Gewichte ein.\n",knz);
  
    
	EingabeA(A,W); 
	KontrollausgabeA(A,W);
  
	while(frage==1)
	{
		ausgeber=1; /* Variable, die in der Pruefschleife beim Erfuelltsein 
		von (*) ggfs.  auf 0 gesetzt wird. */
	
	//Schritt 1
	
		InitialisiereRest(D,V);  
    
		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;
  
		/* Schritt 2*/
	
		for(i=0;i<(KNOTENZAHL-1);i++) //(KNOTENZAHL-1) Hauptschleifendurchlaeufe
		{
			for(u=0;u<KNOTENZAHL;u++)
			{
				for(v=0;v<KNOTENZAHL;v++)
				{
					if(A[u][v]==1  )  //Relax(u,v) fuer alle Kanten (u,v) \in E
					{
						if(D[u]<UNENDLICH &&  (D[u]+W[u][v])<D[v])
						{
							D[v]=D[u]+W[u][v];
							V[v]=u;
						}
					}
				}
			}
		}
    
		// Schritt 3: Pruefschleife
    
		for(u=0;u<KNOTENZAHL;u++)
		{
			for(v=0;v<KNOTENZAHL;v++)
			{
				if(A[u][v]==1 )
				{
					if(D[u]<UNENDLICH &&  (D[u]+W[u][v])<D[v])	
						ausgeber=0;
				}
			}
		} 
       
		if(ausgeber==0)
			printf("Der Graph enthält einen vom Startknoten %hi aus erreichbaren Zyklus mit negativem Gewicht.\n ",(s+1)); 
		else
			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);
}