Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Programmazione 2, 9 CFU => Topic started by: vincenzo86 on 02-12-2010, 17:17:59



Title: Cammino di un grafo matrice adiacenza
Post by: vincenzo86 on 02-12-2010, 17:17:59
Come da oggetto, qualcuno sa come trovare un cammino da un nodo start a un nodo finale?


Title: Re:Cammino di un grafo matrice adiacenza
Post by: matteobuffa on 02-12-2010, 17:27:16
Dijkstra (http://"http://it.wikipedia.org/wiki/Algoritmo_di_Dijkstra") è una possibilità. Ma questo ti trova il cammino minimo e si basa su un grafo orientato e pesato. Forse te cerchi un algoritmo che cerca solo di capire se esiste un percorso da S a F (Sorgente e Fine).

Matteo


Title: Re:Cammino di un grafo matrice adiacenza
Post by: vincenzo86 on 02-12-2010, 17:48:37
Dijkstra (http://"http://it.wikipedia.org/wiki/Algoritmo_di_Dijkstra") è una possibilità. Ma questo ti trova il cammino minimo e si basa su un grafo orientato e pesato. Forse te cerchi un algoritmo che cerca solo di capire se esiste un percorso da S a F (Sorgente e Fine).

Matteo
Appunto, già avevo visto l'algortimo di Dijkstra, ma non mi serve calcolare il cammino minimo, bensì dovrei stampare il percorso da un nodo start a un nodo fine, una sorta di dfs modificata.


Title: Re:Cammino di un grafo matrice adiacenza
Post by: matteobuffa on 02-12-2010, 17:58:51
Questo link (http://www.dis.uniroma1.it/~sassano/Dispense/POR/Visite.pdf) dovrebbe esserti utile allora.

Matteo


Title: Re:Cammino di un grafo matrice adiacenza
Post by: vincenzo86 on 02-12-2010, 18:02:09
Questo link (http://"www.dis.uniroma1.it/~sassano/Dispense/POR/Visite.pdf") dovrebbe esserti utile allora.

Matteo
Non funziona il link .whistling


Title: Re:Cammino di un grafo matrice adiacenza
Post by: matteobuffa on 02-12-2010, 18:04:44
Ora si  :pray

Matteo


Title: Re:Cammino di un grafo matrice adiacenza
Post by: vincenzo86 on 02-12-2010, 18:19:36
Grazie ora gli do un'occhiata


Title: Re:Cammino di un grafo matrice adiacenza
Post by: vincenzo86 on 02-12-2010, 22:10:44
Questo link (http://"www.dis.uniroma1.it/~sassano/Dispense/POR/Visite.pdf") dovrebbe esserti utile allora.

Matteo
Non funziona il link .whistling
Secondo te questo codice potrebbe funzionare?
Code:
public void cammino(NodoMA start,NodoMA end)
        {
            if(isEmpty())
            {
                System.out.println("Grafo vuoto");
            }
            else
            {
                NodoL aux=nodi.getHead();
                for(;aux!=null;aux=aux.next)
                    ((NodoMA)aux.getInfo()).setStato(0);
                System.out.println("INIZIO cammino da "+start+" a "+end);
                ListaL lista=new ListaL();
                boolean cammino=stampaCammino(start,end,lista);
                lista.printList();
                if(lista.getSize()<=1)
                    System.out.println("FINE. Peso cammino: infinito");
                else
                    System.out.println("FINE. Peso cammino: ");

            }
        }
        public boolean stampaCammino(NodoMA n,NodoMA end,ListaL lista)
        {
            if(n.compareTo(end)==0)
            {
                lista.insertTail(n);
                return true;
            }
            if(n.getStato()==0)
            {
                lista.insertTail(n);
                n.setStato(1);
                NodoL aux=this.nodiAdiacenti(n).getHead();   //vado a prendere i nodiadiacenti a n e prendo la testa di questa lista
                for(;aux!=null;aux=aux.getNext())
                    if((stampaCammino((NodoMA)aux.getInfo(),end,lista)))  //se è vera tale istruzione, ritorno true esiste cammino
                    {
                       
                        return true;
                    }
                lista.deleteTail();
            }
            return false;
        }

Grazie