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:
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
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:
Java:
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
