Grafos

ejemplo programa-caminos
import adts.*;import java.util.*;/** * Clase que contiene algoritmos de caminos minimos en grafos*/        public class Caminos        {/** * Algoritmo del calculo del camino minimo sin pesos*/        public static <V,A> CaminoSinPesos caminoMinimoSinPesos        (Grafo<V,A> g, int origen, int destino) throws NoExiste,IdIncorrecto        {//inicializaciones        LinkedList<Integer> procesar= new LinkedList<Integer>();        int[] anterior= new int[g.numVertices()];        boolean[] visitado= new boolean[g.numVertices()];// todas las casillas valen vale false por omision en Java        procesar.addLast(new Integer(origen));        visitado[origen]=true;        anterior[origen]=-1; // para indicar que no tiene        while(!procesar.isEmpty()) {                    int v=procesar.removeFirst().intValue();                    List<Arista<A>> adj=g.listaAristas(v);                    for (Arista a:adj) {                            int dest=a.destino();                            if (!visitado[dest]) {                                    anterior[dest]=v;                                    if (dest==destino){                                        // hemos encontrado el camino minimo                                        return caminoDe(origen,destino,anterior,g);                                     }                                    visitado[dest]=true;                                    procesar.addLast(dest);                                }                        }            }// el destino no ha sidohallado)        throw new adts.NoExiste();        }/** * Metodo para formar el camino sin pesos*/        private static CaminoSinPesos caminoDe(int origen, int destino,         int[] anterior, Grafo g)         {            CaminoSinPesos cam= new CaminoSinPesos(g);            int v=destino;            while (anterior[v]!=-1){                        cam.inserta(v);                        v=anterior[v];            }             cam.inserta(origen);            return cam;}/*** Clase interna para los objetos a almacenar en la cola de prioridad en el algoritmo del camino minimo con pesos*/            static class SubCamino implements Comparable<SubCamino> {             int dest;            double peso;            SubCamino (int dest, double peso) {            this.dest=dest;            this.peso=peso;            }            public int compareTo(SubCamino otro) {                if (this.peso<otro.peso) {                    return -1;             } else                         if (this.peso>otro.peso) {                            return 1;                     } else {                            return 0;            }        }    }/*** Algoritmo del calculo del camino minimo con pesos*/        public static <V> CaminoConPesos caminoMinimoConPesos        (Grafo<V,Double> g, int origen, int destino) throws NoExiste, IdIncorrecto        {        // inicializaciones        PriorityQueue<SubCamino> procesar= new PriorityQueue<SubCamino>();        int[] anterior= new int[g.numVertices()];        double[] peso= new double[g.numVertices()];        boolean[] procesado= new boolean[g.numVertices()];// valor por omision es falsepara todas sus casillas// dar valor infinito a todas las casillas de peso        for (int i=0; i<peso.length; i++) {                peso[i]=Double.POSITIVE_INFINITY;         }        procesar.add(new SubCamino(origen,0.0));        peso[origen]=0.0; // para no hacer ciclos        anterior[origen]=-1; // para indicar que no tiene// bucle para procesar vertices        while (!procesar.isEmpty()) {                    int v=procesar.remove().dest;            if (! procesado[v]) {                procesado[v]=true;                List<Arista<Double>> adj=g.listaAristas(v);            for (Arista<Double> a: adj) {                  int dest=a.destino();                  double...