Witam. Mam następujący problem: Przy algorytmie wyszukiwania najbezpieczniejszej drogi(zmodyfikowana Dijkstra) dla zadanych danych testowych przy największym teście kończy się pamięć.
Komunikat wygląda następująco:
** Exception in thread "main" java.lang.OutOfMemoryError: Java heap space **
i wskazuje na poniższą linię(w tym wypadku tworzy się macierz 100k x 100k):
double MacierzSasiedztwa[][] = new double[liczbaSkrzyzowan][liczbaSkrzyzowan];
Dodanie " -Xms2048M -Xmx4096M" do VM Options nie pomogło.
Poniżej kod programu:
package miasto3;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Locale;
import java.util.Scanner;
public class Miasto3 {
public static int liczbaSkrzyzowan;
public static int liczbaUlic;
public static long liczbaZapytan;
public static double Dijkstra(double MacierzSasiedztwa[][], int poczatek, int koniec)
{
double Miasto[][] = new double[MacierzSasiedztwa.length][MacierzSasiedztwa.length];
double prawd[] = new double[MacierzSasiedztwa.length];
int odwiedzone[] = new int[MacierzSasiedztwa.length];
double minprawd;
int nast = 0;
for(int i=0;i<MacierzSasiedztwa.length;i++)
{
System.arraycopy(MacierzSasiedztwa[i], 0, Miasto[i], 0, MacierzSasiedztwa.length);
}
for(int i=0;i<MacierzSasiedztwa.length;i++)
{
prawd[i]=Miasto[poczatek][i];
odwiedzone[i]=0;
}
for(int i = 0; i<MacierzSasiedztwa.length;i++)
{
for(int j=0; j<Miasto.length;j++)
{
if(i==j)
Miasto[j][i]=0;
if(MacierzSasiedztwa[i][j]!=0)
Miasto[j][i]=MacierzSasiedztwa[i][j];
}
}
prawd[poczatek]=1;
odwiedzone[poczatek]=1;
while(odwiedzone[koniec]==0)
{
minprawd=0;
for(int i=0;i<MacierzSasiedztwa.length;i++)
{
if(prawd[i]>=minprawd && odwiedzone[i]==0)
{
minprawd=prawd[i];
nast=i;
}
}
odwiedzone[nast]=1;
for(int i=0;i<MacierzSasiedztwa.length;i++)
{
if(odwiedzone[i]==0)
if(minprawd*Miasto[nast][i]>=prawd[i])
prawd[i]=minprawd * Miasto[nast][i];
}
}
return prawd[koniec];
}
public static void main(String[] args) throws FileNotFoundException {
//PrintWriter zapis = new PrintWriter("out.txt");
File wejscie = new File("ind.txt");
Scanner scan = new Scanner(wejscie).useLocale(Locale.US);
java.text.DecimalFormat df=new java.text.DecimalFormat();
df.setMaximumFractionDigits(15); //dla df ustawiamy największą ilość miejsc po przecinku
df.setMinimumFractionDigits(15); //
liczbaSkrzyzowan = scan.nextInt();
liczbaUlic = scan.nextInt();
liczbaZapytan = scan.nextInt();
//System.out.println("Liczba skrzyzowan: " + liczbaSkrzyzowan);
//System.out.println("Liczba skrzyzowan: " + liczbaUlic);
//System.out.println("Liczba skrzyzowan: " + liczbaZapytan);
double MacierzSasiedztwa[][] = new double[liczbaSkrzyzowan][liczbaSkrzyzowan];
for(int i = 0; i<liczbaUlic;i++)
{
int x=scan.nextInt();
int y=scan.nextInt();
double w= Math.abs(1- scan.nextDouble());
MacierzSasiedztwa[x-1][y-1] = w;
}
for(int i = 0; i<MacierzSasiedztwa.length;i++)
{
for(int j=0; j<MacierzSasiedztwa.length;j++)
{
if(i==j)
MacierzSasiedztwa[j][i]=0;
if(MacierzSasiedztwa[i][j]!=0)
MacierzSasiedztwa[j][i]=MacierzSasiedztwa[i][j];
}
}
int wyw1;
int wyw2;
long lz = liczbaZapytan-1;
// System.out.println(lz);
double wynik = 0;
for(int i=0;i<=lz;i++)
{
wyw1 = scan.nextInt();
wyw2 = scan.nextInt();
int pom1 = wyw1-1;
int pom2 = wyw2-1;
//System.out.println("Wywołanie nr " + i + " dla : "+ (pom1+1) + " " + (pom2+1));
System.out.println(df.format(1 - Dijkstra(MacierzSasiedztwa, pom1 ,pom2)));
//wynik = (1 - Dijkstra(MacierzSasiedztwa, pom1 ,pom2));
//zapis.println(wynik);
//System.out.println(wynik);
}
// System.out.println(1 - Dijkstra(MacierzSasiedztwa, 4 ,20));
// zapis.close();
}
}
W załączeniu plik testowy.
Dodam, że dla mniejszych testów program działa bezbłędnie.
Skończyły mi się pomysły.
Z góry dziękuję za porady.