GRAFOS

Implementación en Java
/**
* Calcular el camino mínimo en un grafo
*/
public static CaminoConPesos caminoMinimoAciclico
(Grafo g, int origen, int destino)
throws NoExiste, IdIncorrecto, HayCiclos
{
int anterior[]= new int[g.numVertices()];
double[] peso= new double[g.numVertices()];
// dar valor infinito a todas las casillas de peso
for (int i=0; i procesar =
new LinkedList();
int procesados=0;
// insertar en la cola vértices de grado cero
for (int v=0; v> ady=g.listaAristas(v);
for (Arista a: ady) {
int dest=a.destino();
grado[dest]--;
if (grado[dest]==0) {
procesar.addLast(new Integer(dest));
}
if (!Double.isInfinite(peso[v])) {
double p=a.contenido().doubleValue();
if (peso[dest]>peso[v]+p) {
anterior[dest]=v;
peso[dest]=peso[v]+p;
}
}
}
}
if (procesados!=g.numVertices()) {
throw new HayCiclos();
}
if (Double.isInfinite(peso[destino])) {
throw new NoExiste();
} else {
return caminoDe
(origen,destino,anterior,peso[destino],g);
}
}