[JAva] problema con i grafi

[dungedra]

In un aeroporto vi sono n gate, ciascuno dei quali è individuato da un codice
I gate possono essere collegati tra loro per mezzo di corridoi bidirezionali ciascuno avente un certo costo di manutenzione. (il costo di manutenzione rappresenta il peso dell’arco)
ipotizzare un funzionamento a regime):

funzione “risparmio della spesa” che restituisce se esiste l’elenco minimo dei corridoi da lasciare attivi per garantire che tutti i gate siano raggiungibili da ogni altro gate e tale da assicurare un costo minimo di manutenzione totale.

inizio risoluzione:


public class gate{
protected String codice;
public gate(String codice){
this.codice=codice;
}
}

public class aereoporto {
private GrafoNOLP G;
private Vettass<gate> v;
public aereoporto(int n){
G=new GrafoNOLP(n);
v=new Vettass<gate>(n);
}
public LinkedList<Arco> risparmioSpesa(){
LinkedList<Arco>L=new LinkedList();
.
.
.
return L;
}
}



essendo che mi viene richiesto il costo di trasferimento minimo, cioè il peso minimo,mi verrebbe in mente di usare Dijkstra…pero non saprei come fare a ricavarmi gli archi da non cancellare e da fare rimanere attivi…
per quanto riguardava di fatto di essere raggiungibili da ogni altro gate, pensavo di usare la funzione esisteCammmino, ciclando i nodi del grafo attraverso un ciclo for annidato…

è un po tutto campato in aria, ma non chiedo la risoluzione anche se sarebbe ben accetta, ma qualche idea che mi chiarisca come fare..


per il grafo posso utilizzare i seguenti metodi

Si possono usare i package standard di Java (Vedere in particolare il package java.util
su http://java.sun.com/j2se/1.4.2/docs/...-summary.html). Per tutto il
resto fare riferimento ai testi consigliati.
package Grafi;

public interface Grafo {
public int numNodi(); // restituisce num. nodi
public int numArchi(); // restituisce num. archi
public LinkedList<Arco> archi(); // rest. elenco archi del grafo
public LinkedList<Arco> adiacenti(int v); // rest. lista degli archi uscenti da v
public boolean esisteArco (int x, int y); // verifica esistenza arco fra x ed y
public boolean aggiungiArco(int x, int y); // ins. arco fra x ed y
public boolean rimuoviArco(int x, int y); // rimuove arco fra x ed y
public ArrayList<Boolean>VisitaDFS(int x); // DFS (similm. BFS)a partire da x
public ArrayList<Integer>Dijkstra(int x); // Dijkstra a partire da x
public boolean esisteCammino (int x, int y); // ver. esistenza cammino fra x ed y
}
-------------------------------------------------------------------------------
Le classi GrafoOL, GrafoOM, GrafoNOL, GrafoNOM implementano l’interfaccia Grafo
-------------------------------------------------------------------------------
public class Arco {
public int orig, dest;
public Arco(int x, int y) {orig = x; dest = y;}
}
-------------------------------------------------------------------------------
public class ArcoP extends Arco{
public int orig, dest, peso;
public ArcoP(int x, int y, int p) {super(x,y); peso = p;}
}
-------------------------------------------------------------------------------
public class GrafoOLP extends GrafoOL implements Grafo;
// restituisce true se l'arco esiste col peso specificato altrimenti false
public boolean esisteArcoPesato (int x, int y, int p);
// inserisce arco fra x ed y col peso specificato
public void aggiungiArcoPesato (int x, int y, int p);
// rimuove arco fra x ed y e fissa il peso a 0
public void rimuoviArcoPesato (int x, int y);
rimuoviArco(x,y); matricePesi[x][y] = 0;
// restituisce il peso dell'arco
public int peso(int x,int y);
-------------------------------------------------------------------------------
public class GrafoOMP extends GrafoOM implements Grafo;
// La stessa interfaccia di GrafoOLP. Idem per GrafoNOLP e GrafoNOMP
----------------------------------------------------------------------------------------
GrafoOM g = new GrafoOM(100); // Esempio di uso del costruttore
// scansione degli adiacenti del nodo 0
ListIterator<Arco> e = g.adiacenti(0).listIterator();
while (e.hasNext()){
Arco a = e.next();
g.rimuoviArco(a.orig, a.dest);
}

// scansione del grafo per nodi
for (int i = 0; i < g.numNodi(); i++)
; // ...
GrafoOLP g1 = new GrafoOLP(100);
// scansione del grafo per archi per impostarli tutti a 1
ListIterator<Arco> e1 = g1.archi().listIterator();
while (e1.hasNext()){
ArcoP a = (ArcoP) e1.next();
a.peso = 1; // errato
g1.aggiungiArcoPesato(a.orig, a.dest, 1); // corretto
}
-------------------------------------------------------------------------------------
public class Vettass<T>; // Vettore associativo
Interfaccia simile a java.util.Map.

[bepp10]

Ciao Dungedra,

hai poi risolto il problema della risoluzione della funzione "risparmio della spesa"?
Se si, mi potresti aiutare? Debbo risolvere un compito universitario in cui, molto probabilmente, ci sarà.

Ti ringrazio anticipatamente.

Ciao.