# einfacher Routenplaner in Eclipse (Dijkstra)



## dasmacks (27. Apr 2012)

Hi Leute,
ist zwar nicht wirklich ne Hausaufgabe passt aber glaube am besten hier rein.

Es geht um die Programmierung eines einfachen Routenplanners in Eclipse. Ziel ist die Erstellung eines Programms zur Berechnung von kürzesten Wegen. Basis der Berechnung soll der Dijkstra-Algorithmus sein. Der Benutzer des Programms soll zur Eingabe von beliebig vielen Knoten und deren Kanten aufgefordert weden. Dannach legt er einen Startknoten und einen Zielknoten fest. Das Programm soll nun die kürzesten Verbindung berechnen und ausgeben.

Bis jetzt haben wir folgendes zusammengebastelt:


```
import java.util.Scanner;
public class dijkstra3 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub


		

		int x,s,e;
		String st, en;
		Scanner sca = new Scanner(System.in);
		System.out.println("Zahl der Knoten eingeben");
		x = sca.nextInt();
		
		String [] name = new String [x];
		int [][] werte = new int[x][x];



		for (int i=0;i<x;i++){
		System.out.println("Geben Sie den Namen des " + (i+1) +". Knoten ein: ");
		name[i] = sca.next();
		}

		for (int i=0;i<x;i++){
		 
		}
	 

		for (int i=0;i<x;i++){
		System.out.println("Geben Sie die benötigte Zeit von " + name[i]);
			for (int j=0;j<x;j++){
			System.out.println("nach " +  name[j] + " ein");
			werte[i][j]=sca.nextInt();
		}
		}

		 
		
		s=0;
		System.out.println("Startort eingeben");
		st = sca.next();
		for (int i=0;i<x;i++){
		if (st.equals(name[i]))
		           s=i;
		};
		e=0;
		System.out.println("Endort eingeben");
		en = sca.next();
		for (int i=0;i<x;i++){
			if (en.equals(name[i]))
			           e=i;
			};	
		
		
		int z=Integer.MAX_VALUE/2;
		
		
		int size=werte.length;
		

		
		int [] pArr=	new int [size];
		int dArr[]=new int [size];	
		boolean vArr[]=new boolean [size];	
		boolean eArr[]=new boolean [size];
		
		
		
		for (int i = 0; i < pArr.length; i++)
		{
			pArr[i]=-1;
		}
		
		pArr[s]=s;
		
		
		for (int i = 0; i < dArr.length; i++)
		{
			dArr[i]=z;
		}
		
		dArr[s]=0;
			
		for (int i = 0; i < vArr.length; i++)
		{
			vArr[i]=false;
		}
		vArr[s]=true;
			
		for (int i = 0; i < eArr.length; i++)
		{
			eArr[i]=false;
		}
		
		
		while(!mvLeer(vArr))
		{
			int i=dMinAusMV(vArr, dArr);
			vArr[i]=false;
			eArr[i]=true;
			
			for (int k = 0; k < werte[i].length; k++)
			{
				if(!eArr[k]&&werte[i][k]<z)
					
					
					
					if(dArr[k]>dArr[i]+werte[i][k])
					{
						dArr[k]=dArr[i]+werte[i][k];
						pArr[k]=i;
						vArr[k]=true;
					}
				
			}			
			
			
		}
		
		for (int i = 0; i < dArr.length; i++)
		{
			if (i ==e)
			System.out.println("Entfernung von " +name[s] +" zu "+name[i]+" beträgt "+dArr[i]);
		}
		System.out.println();
		
		
	}
	
	static boolean mvLeer(boolean []mv) 
	{
		for (int i = 0; i < mv.length; i++)
		{
			if(mv[i])
				return false;
		}
		return true;
	}
	
	static int dMinAusMV(boolean [] mv, int []dArr)
	{	
		
		int v=0;
		while(v<mv.length&&!mv[v])
			v++;
		
		int indexK=v;
		for (int p = 1; p < mv.length; p++)
		{
			if(mv[p]==true)
				if(dArr[p]<dArr[indexK])
					indexK=p;
				
		}
		
		return indexK;
	}

}
```

Was könnte man denn noch verbessern?
Und wie bekommen wir es hin, dass die Route (also die einzeln durchlaufenen Knoten) angezeigt wird)
Würd mich über Antworten freuen!

Grüße 

Max


----------



## Marcinek (27. Apr 2012)

Dein Code verstöst gegen fast alle Java Konventionen, die ich kenne.

Sieht für mich "hingeklascht" aus. Da werde ich sicherlich nicht die Mühe machen da Verbesserungen vorzuschlagen.

Graphen kann man hiermit visualisieren: Welcome to JGraphT - a free Java Graph Library


----------



## Fab1 (27. Apr 2012)

Du könntest dem ganzen mal versuchen etwas Struktur zu verleihen. Eine Klasse mit 160 Zeilen ist nicht wirklich schön.


----------



## Landei (27. Apr 2012)

Die 160 Zeilen sind nicht das Problem, sondern das über 120 davon zur main-Methode gehören. Eine recht ordentliche Implementierung findest du hier, vergleiche sie mal mit deiner.


----------

