• Author / Uploaded
• Alfredo Parra Urrea

Citation preview

Facultad Ciencias Empresariales. Escuela de Ingeniería Civil Informática. Chillan.

Tarea de Análisis y Diseños de Algoritmos.

“ALGORITMO DE JOHNSON”

Integrantes:

Alfredo Parra Urrea. Carlos San Juan Contreras.

Profesor:

Pablo Sáez González.

Fecha:

12-octubre-2011

2

Introducción En el análisis de algoritmos muchas veces nos encontramos con problemas difíciles de resolver o simplemente no hallamos las herramientas adecuadas para poder desarrollar dichos inconvenientes. Entre los grandes problemas que nos podemos topar, están los grafos, ya que son difíciles de analizar, producto de sus múltiples formas y gran variedad de estos, hay grafos simples, grafos completos, grafo conexo, inconexo, dirigidos, entre varios otros. Por esto mismo estudiarlos ya sea por sus estructuras, tipo y/o su complejidad debido a que son esenciales para encontrar respuestas a complicaciones cotidianas tan simples como encontrar rutas cortas entre puntos de un mapa. Es por ello que muchas personas han querido diseñar algoritmos que nos permitan evaluar y analizar los diferentes grafos, para así tener la mejor solución de forma más rápida. Existen varias herramientas para grafos específicos, encontramos los algoritmos de DIJKSTRA que es un algoritmo usado para encontrar los caminos mínimos de un grafo dirigido ponderado de “N” nodos no aislados, donde sea “x” el nodo inicial, un vector “D” de tamaño “N” guardará el final del algoritmo las distancia desde “x” al resto de los nodos. También otro algoritmo usado para resolver grafos es el de Bellman-Ford que se usa para encontrar el camino minimo de un grafo dirigido ponderado, el cual puede poseer aristas negativas, a diferencia con Dijkstra.

Donald Johnson tuvo la inquietud de resolver grafos dirigidos dispersos, y decidió mezclar los algoritmos de Dijkstra y Bellman-Ford para poder realizar este nuevo algoritmo llamado Algoritmo de Johnson en su honor. Este informe apunta al trabajo que hizo Johnson explicando cómo realizo su algoritmo.

3

Algoritmo de Johnson y Comentarios. Clase AdjacencyListGraph: package algoritmojohnson; /** * @author Alfredo Parra y Carlos San Juan */ import java.util.Iterator; public class AdjacencyListGraph implements Graph { //verificamos si el grafo es o no direccionado protected boolean directed; /* El índice del último vértice agregado a esta gráfica. */ protected int lastAdded; /*cantidad de aristas*/ protected int e; /** lista adjacente */ protected AdjListInfo[] adj; /** recibimos la cantidad de vertices y si el grafico es direccionado o no */ public AdjacencyListGraph(int cardV, boolean directed) { this.directed = directed; lastAdded = -1; adj = new AdjListInfo[cardV]; e = 0; } /*inicializa los vertices con un nombre*/ public Vertex addVertex(String name) { lastAdded++; // the index for this vertex adj[lastAdded] = new AdjListInfo(new Vertex(lastAdded, name)); return adj[lastAdded].thisVertex; } /** asigna indice y nombre al vertice */ public Vertex addVertex(int index, String name) { lastAdded = index; adj[lastAdded] = new AdjListInfo(new Vertex(lastAdded, name)); return adj[lastAdded].thisVertex; } /*agragamos un nuevo vertice */ public Vertex addVertex(Vertex v) { if (v.getIndex() == Vertex.UNKNOWN_INDEX) {

4

lastAdded++; v.setIndex(lastAdded); } else { lastAdded = v.getIndex(); } adj[lastAdded] = new AdjListInfo(v); return v;

} /*retorna el vertice que posee el mismo "index" */ public Vertex getVertex(int index) { return adj[index].thisVertex; } /*va verificando un vertice con los otros

*/

public void addEdge(Vertex u, Vertex v) { // Put v on u's list. int uIndex = u.getIndex(); Edge x = new Edge(v, adj[uIndex].head); adj[uIndex].head = x; // If undirected, put u on v's list. if (!directed) { int vIndex = v.getIndex(); x = new Edge(u, adj[vIndex].head); adj[vIndex].head = x; } e++; } /*va comparando el index de u con los otros de v */ public void addEdge(int u, int v) { // poner v en la lista de u Edge x = new Edge(adj[v].thisVertex, adj[u].head); adj[u].head = x; // Si no es dirigido, poner u en la lista v if (!directed) { x = new Edge(adj[u].thisVertex, adj[v].head); adj[v].head = x; } e++; } /*Clase interna de la matriz de lista de adyacencia. */ protected static class AdjListInfo { /** El vértice de adyacencia, cuya lista es esto. */ public Vertex thisVertex; /** El primer borde en la lista de adyacencia de este vértice.*/

5

public Edge head; /* Crea que un objeto de tipo AdjListInfo vacio*/ public AdjListInfo(Vertex v) { thisVertex = v; head = null; } } /*Clase interna de los bordes lista de adyacencia. Listas de adyacencia son simplemente enlazada.*/ protected static class Edge { public Vertex vertex; public Edge next; /** Crea un nuevo borde. v El lado del vértice. succesor borde sucesor de éste. */ public Edge(Vertex v, Edge successor) { vertex = v; next = successor; } } //retornamos el iterador que pesa los vertices del grafo public Iterator vertexIterator() { return new VertexIterator(); } /*Clase interna para el vertice itertor */ public class VertexIterator implements Iterator { /** El índice del vértice devuelto por la llamada más reciente Inicialmente, su valor es -1.*/ protected int lastVisited; /** Inicia una iteración a través de los vértices */ public VertexIterator() { lastVisited = -1; } /*verifica si hay el iterator tiene más vertices */ public boolean hasNext() { return lastVisited < adj.length - 1; } /** Devuelve el siguiente vértice en la iteración.*/ public Object next() { return adj[++lastVisited].thisVertex; }

6

public void remove() {//verifica errores throw new UnsupportedOperationException(); } } public Iterator edgeIterator(Vertex u) { return new EdgeIterator(u.getIndex()); } public Iterator edgeIterator(int u) { return new EdgeIterator(u); } /*Clase interna para un iterador que recorre las aristas incidentes en un vértice dado.*/ public class EdgeIterator implements Iterator { /*retorna el borde de la llamada más reciente*/ protected Edge current; /*El índice del vértice cuyos bordes este iterador recorre.*/ protected int index; /*Inicia una iteración a través de las aristas incidentes en un vértice dado. donde v es un indice*/ public EdgeIterator(int v) { index = v; current = null; } /*verifica si hay más vertices */ public boolean hasNext() { if (current == null) { return adj[index].head != null; } else { return current.next != null; } } /*Devuelve el siguiente borde de la iteración*/ public Object next() { if (current == null) { current = adj[index].head; } else { current = current.next; } return current.vertex; } /*en caso de errores

7

*/ public void remove() { throw new UnsupportedOperationException(); } } /** retorna el numero de vertices*/ public int getCardV() { return adj.length; } /*retorna el número de bordes */ public int getCardE() { return e; } /*verifica si el grafo es o no dirigido*/ public boolean isDirected() { return directed; } /** Crea y devuelve un gráfico que utiliza el mismo conjunto de * vértices en la gráfica. El gráfico creado no tiene bordes*/ public AdjacencyListGraph useSameVertices() { // inicializa un grafo vacio. AdjacencyListGraph newGraph = makeEmptyGraph(adj.length, directed); //Ahora agregue cada vértice del grafo en el grafo nuevo, //utilizando los objetos de Vertex . for (int i = 0; i < adj.length; i++) { newGraph.addVertex(adj[i].thisVertex); } }

return newGraph;

/** *Crea y devuelve una AdjacencyListGraph vacia * cardV número de vértices y una booleana * directed indica si el grafo es dirigido. */ protected AdjacencyListGraph makeEmptyGraph(int cardV, boolean directed) { return new AdjacencyListGraph(cardV, directed); } /** representa el grafo*/ public String toString() {//imprime las iteraciones String result = ""; Iterator vertexIter = vertexIterator(); while (vertexIter.hasNext()) { Vertex u = (Vertex) vertexIter.next(); result += u + ":\n"; Iterator edgeIter = edgeIterator(u);

8

while (edgeIter.hasNext()) { Vertex v = (Vertex) edgeIter.next(); result += " " + v + "\n"; } } return result; } }

Clase BellmanFord: package algoritmojohnson; import java.util.Iterator; /* * @author Alfredo Parra y Carlos San Juan */ class BellmanFord extends SingleSourceShortestPaths{ /* Establece las variables de instancia, incluida la asignación SpInfo pero no la asignación de los ShortestPathInfo, objetos referenciado por la matriz de initializeSingleSource theGraph para encontrar los caminos más cortos. */ public BellmanFord(WeightedAdjacencyListGraph theGraph){ super(theGraph); } /*Calcula una sola fuente de rutas más cortas desde un origen determinado Vértice, el llenado de los pesos y sus predecesores del tipo SpInfo. También establece la variable de instancia NoNegWeightCycle adecuada, para no encotrar ciclos negativos. "s" La origen vértice. */ public void computeShortestPaths(Vertex s) { initializeSingleSource(s); int cardV = g.getCardV(); // Ejecutar a través de todos los bordes | V | -1 veces. for (int i = 1; i du + w) { noNegWeightCycle = false; return; } } }

}

}

Clase Dijkstra: package algoritmojohnson; import java.util.Vector; /* * @author Alfredo Parra y Carlos San Juan */ class Dijkstra extends SingleSourceShortestPaths { /** *Establece las variables de instancia, incluida la asignación SpInfo pero no la asignación de los ShortestPathInfo, objetos referenciado por la matriz de initializeSingleSource theGraph para encontrar los caminos más cortos. */ public Dijkstra(WeightedAdjacencyListGraph theGraph) { super(theGraph); } /*Calcular una sola fuente rutas más cortas desde un origen determinado vértice, llenando en los pesos y los predecesores de la matriz */ public void computeShortestPaths(Vertex s) { initializeSingleSource(s); Vector recorrido=new Vector(1,1);

10

//crear una cola de prioridad minima minPriorityQueue MinPriorityQueue q = new MinHeapPriorityQueue(); /*La información que estamos manteniendo para cada vértice es un objeto DijkstraInfo. Tenemos que establecer el theVertex y manejar los campos. Mediante la inserción de cada objeto DijkstraInfo en la cola de priorityMin-, tenemos la manija que se almacenan en el objeto.*/ int cardV = g.getCardV(); for (int i = 0; i < cardV; i++) { DijkstraInfo info = (DijkstraInfo) getShortestPathInfo(i); info.theVertex = g.getVertex(i); info.handle = q.insert(info); } q.decreaseKey(((DijkstraInfo) getShortestPathInfo(s)).handle, new Double(0)); System.out.print("Recorrido mas corto: "); while (!q.isEmpty()) { // Encontrar el vértice de la cola con la llave más pequeña. DijkstraInfo uInfo = (DijkstraInfo) q.extractMin(); uInfo.handle = null; //ya no está en la cola Vertex u = uInfo.theVertex; double du = getShortestPathInfo(u).getEstimate(); //Compruebe cada borde incidente. WeightedEdgeIterator edgeIter = g.weightedEdgeIterator(u); while (edgeIter.hasNext()) { Vertex v = (Vertex) edgeIter.next(); DijkstraInfo vInfo = (DijkstraInfo) getShortestPathInfo(v); double weight = edgeIter.getWeight(); if (vInfo.relax(u, du, weight)) { //"v" la ruta más corta de estimación ha cambiado, //por lo que actualizar la cola de priorityMin. q.decreaseKey(vInfo.handle,new Double(vInfo.getEstimate()));

}

} } recorrido.add(u.getName()); } for(int i=0;i= 0; i--) heapify(i); } /*Devuelve un objeto que va al heap usando Heapsort*/ public Sorter makeSorter(){ return new Heapsort(); } /*Implementa Heapsort */ public class Heapsort implements Sorter{ public void sort(Comparable[] arrayToSort) { //Dado que este método está dentro de una clase anidada dentro del //HEAP, debe haber un montón de objetos existentes que podemos utilizar. array = arrayToSort; heapSize = array.length; //hacemos cumplir la propiedad del HEAP buildHeap(); //Hace el resto del algoritmo heapsort. for (int i = array.length-1; i >= 1; i--) { exchange(0, i); heapSize--; heapify(0); } }

}

/*Las clases anidadas para las manijas de un montón. Para ser utilizado por las subclases MinHeapPriorityQueue y MaxHeapPriorityQueue.*/ protected static class Handle implements Comparable{ /* Índice en la matriz HEAP*/ protected int index; /*Información almacenada */ protected DynamicSetElement info; /*Inicializacion de Handle*/ protected Handle(int index, DynamicSetElement info){ this.index = index; this.info = info;

16

} /*compara objetos*/ public int compareTo(Object e){ return info.compareTo(((Handle) e).info); } } }

Clase HeapUnderflowException: package algoritmojohnson; /* @author Alfredo Parra y Carlos San Juan */ /*Clase verifica errores del HEAP*/ public class HeapUnderflowException extends RuntimeException{ }

Clase Johnson: package algoritmojohnson; import java.util.Iterator; /* @author Alfredo Parra y Carlos San Juan */ class Johnson { /*indica un grafo ponderado*/ private WeightedAdjacencyListGraph g; /*verifica si es un grafo dirigido o no*/ private boolean noNegWeightCycle; /*El resultado de ejecutar un algoritmo de Johnson. El objeto ShortestPathInfo en spInfo [u] [v] contiene el peso del camino más corto de u a v, donde u y v son los índices de vértice, junto con el predecesor de v en un camino más corto desde u. Puede consultar esta información llamando a los métodos de la clase ShortestPathInfo. */ private ShortestPathInfo[][] spInfo; /*Inicializa las variables de instancia, a excepción de la asignación de los objetos acutal ShortestPathInfo en spInfo.*/ public Johnson(WeightedAdjacencyListGraph theGraph) { g = theGraph; noNegWeightCycle = true;

}

int n = g.getCardV(); spInfo = new ShortestPathInfo[n][n];

17

/*se verifica si hay ciclos negativos*/ public boolean hasNoNegativeWeightCycle(){ return noNegWeightCycle; } /*Devuelve una referencia al objeto ShortestPathInfo para un determinado par de vértices.*/ public ShortestPathInfo getShortestPathInfo(Vertex u, Vertex v) { return getShortestPathInfo(u.getIndex(), v.getIndex()); } /*Devuelve una referencia al objeto ShortestPathInfo para un determinado par de indices. */ public ShortestPathInfo getShortestPathInfo(int u, int v) { return spInfo[u][v]; } /*Calcula todos los pares de los caminos más cortos usando el algoritmo de Johnson. Los resultados son los objetos ShortestPathInfo referencia a la matriz spInfo, junto con la bandera noNegWeightCycle.*/ public void computeShortestPaths() { /* Hacer un grafo Gprime , que es lo mismo que g, pero con un vértice adicional y bordes 0-peso desde el vértice adicional a todos los otros vértices. El vértice extra "s" es V0, pero aquí vamos a hacer que el índice disponible. Los objetos vértice en G será compartida con Gprime. Por lo que s se encuentra en el índice disponible siguiente, todos los vértices de G tienen el mismo índice, que es necesario*/ int cardV = g.getCardV(); WeightedAdjacencyListGraph gPrime = new WeightedAdjacencyListGraph(cardV+1, true); Iterator vertexIter = g.vertexIterator(); while (vertexIter.hasNext()) gPrime.addVertex((Vertex) vertexIter.next()); Vertex s = new Vertex("s"); gPrime.addVertex(s); vertexIter = g.vertexIterator(); while (vertexIter.hasNext()) { Vertex u = (Vertex) vertexIter.next(); WeightedEdgeIterator edgeIter = g.weightedEdgeIterator(u); while (edgeIter.hasNext()) gPrime.addEdge(u, (Vertex) edgeIter.next(), edgeIter.getWeight()); gPrime.addEdge(s, u, 0); } System.out.println("Grafo con nodo nuevo 's':\n"); //crea un nodo nuevo llamado "s" System.out.println(gPrime);// y los conecta a todos con peso cero

18

//Ejecutar el algoritmo de Bellman-Ford en Gprime de la fuente. BellmanFord bf = new BellmanFord(gPrime); bf.computeShortestPaths(s); if (bf.hasNoNegativeWeightCycle()) { /*El gráfico no contiene un ciclo negativo de peso, por lo que puede proceder. Calcular los valores de h para todos los vértices en Gprime.*/ System.out.println("Muestra los nuevos pesos h(v)\n"); double[] h = new double[cardV+1]; for (int i = 0; i = array.length) { Comparable[] temp = new Comparable[heapSize * 2]; for (int i = 0; i < heapSize; i++) temp[i] = array[i]; array = temp; } //Crear una nueva "Handle", y lo puso en el índice disponible. Handle handle = new Handle(heapSize, x); array[heapSize] = handle;

25

heapSize++; //Burbuja hasta la pila. bubbleUp(heapSize-1); //devuelve el handle return handle; } /*Devuelve el elemento más pequeño en la cola de prioridad min-sin eliminar el elemento.*/ public DynamicSetElement minimum() throws HeapUnderflowException{ if (heapSize > 0) return ((Handle) array[0]).info; else { throw new HeapUnderflowException(); } } /*Quita y devuelve el elemento más pequeño en la cola de prioridad min. Con el fin de la "manija" del elemento volvió a ser elegible para la recolección de basura, el usuario de la MinPriorityQueue debe incluir en los datos de un satélite DynamicSetElement es una referencia a la "manija". Esta referencia se debe establecer en nulo para el elemento devuelto por extractMin. */ public DynamicSetElement extractMin(){ if (heapSize < 1) throw new HeapUnderflowException(); // Obtenga una referencia al elemento más pequeño. DynamicSetElement min = ((Handle) array[0]).info; //Mueva el último elemento de la pila a la raíz, y claro //la referencia en su posición actual de la matriz. array[0] = array[heapSize-1]; ((Handle) array[0]).index = 0; array[heapSize-1] = null; heapSize--; // restaura las propiedades del min-heap heapify(0); return min;

// all done

} /* Disminuye la clave de un elemento dado a un nuevo valor.*/ public void decreaseKey(Object element, Comparable newKey) throws KeyUpdateException { Handle handle = (Handle) element; if (newKey.compareTo(handle.info.getKey()) > 0) throw new KeyUpdateException();

26

handle.info.setKey(newKey); // seleccionar nueva clave bubbleUp(handle.index); // restaurar la propiedad min-heap }

}

/*Bubbles ordena el elemento en un índice dado en la pila hasta que sea mayor o igual a su padre.*/ private void bubbleUp(int i) { while (i > 0 && array[parent(i)].compareTo(array[i]) > 0) { exchange(i, parent(i)); i = parent(i); } }

Clase MinPriorityQueue: package algoritmojohnson; /* @author Alfredo Parra y Carlos San Juan */ public interface MinPriorityQueue { /*Inserta un elemento dinámico, puesto en la cola de prioridad min.*/ public Object insert(DynamicSetElement x); /*Devuelve el elemento más pequeño en la cola "min-priority" sin la eliminación del elemento.*/ public DynamicSetElement minimum(); public DynamicSetElement extractMin(); /*Quita y devuelve el elemento más pequeño en la cola de prioridad min.*/ public void decreaseKey(Object element, Comparable newKey) throws KeyUpdateException; /*verifica si esta vacia */ public boolean isEmpty(); }

Clase ShortestPathInfo: package algoritmojohnson; /* @author Alfredo Parra y Carlos San Juan */ class ShortestPathInfo { private double d; /* El predecesor actual (padre) para este vértice.*/ private Vertex pi;

27

/* Inicializa el cálculo de ruta más corta hasta el infinito y el predecesor de nulo. */ public ShortestPathInfo(){ d = Double.POSITIVE_INFINITY; pi = null; } /*Establece la estimación de la ruta más corta.*/ public void setEstimate(double newEstimate) { d = newEstimate; } /*Devuelve el cálculo de ruta más corta.*/ public double getEstimate(){ return d; } /*Establece el predecesor.*/ public void setPredecessor(Vertex v){ pi = v; } /** Retorna el predecesor. */ public Vertex getPredecessor() { return pi; } /*relaja un borde*/ public boolean relax(Vertex u, double du, double w){ double newWeight = du + w; if (newWeight < d) { d = newWeight; pi = u; return true; } else return false; } /*retorna la representacion de este objeto*/ public String toString() { String parentName; if (pi == null) parentName = "(null)"; else parentName = pi.getName(); return "d = " + d + ", pi = " + parentName; }

}

28

Clase SingleSourceShortestPaths: package algoritmojohnson; abstract public class SingleSourceShortestPaths{ /*El gráfico que se está calculando una sola ruta de los caminos más cortos. */ protected WeightedAdjacencyListGraph g; //verifica si el grafo es dirigido protected boolean noNegWeightCycle; /* El resultado de ejecutar el algoritmo para la ruta más corta. Cada objeto de esta matriz corresponde a un vértice de la gráfica, y puede consultar sus respuestas llamando a los métodos de la clase ShortestPathInfo.*/ private ShortestPathInfo[] spInfo; /*Establece las variables de instancia, incluida la asignación de la matriz spInfo pero no la asignación de los objetos ShortestPathInfo referencia a la matriz.*/ protected SingleSourceShortestPaths(WeightedAdjacencyListGraph theGraph) { g = theGraph; noNegWeightCycle = true; //no han encontrado todavía una spInfo = new ShortestPathInfo[g.getCardV()]; } /*Calcula una sola fuente de rutas más cortas desde un origen determinado vértice, el llenado de los pesos y los predecesores de la matriz spInfo. */ abstract public void computeShortestPaths(Vertex s); /*inicializa la ruta más corta*/ public void initializeSingleSource(Vertex s){ for (int i = 0; i < spInfo.length; i++) spInfo[i] = newShortestPathInfo(); getShortestPathInfo(s).setEstimate(0); } /** retorna un nuevo objeto*/ protected ShortestPathInfo newShortestPathInfo(){ return new ShortestPathInfo(); } /*detecta ciclos negativos */ public boolean hasNoNegativeWeightCycle() { return noNegWeightCycle; } /*retorna la ruta más corta*/

29

public ShortestPathInfo getShortestPathInfo(Vertex v) { return getShortestPathInfo(v.getIndex()); }

}

/*Retorna una referencia de un objeto ShortestPathInfo para un vertice*/ public ShortestPathInfo getShortestPathInfo(int v){ return spInfo[v]; }

Clase Sorter: package algoritmojohnson; /* @author Alfredo Parra y Carlos San Juan */ public interface Sorter{ /*Ordena una matriz de objetos comparables.*/ public void sort(Comparable[] array); }

Clase Vertex: package algoritmojohnson; /* @author Alfredo Parra y Carlos San Juan */ public class Vertex { /*Valor que indica que este vértice aún no cuenta con un índice, es decir, el índice se desconoce. */ public static final int UNKNOWN_INDEX = -1; /* Índice de este vértice de su gráfica, de 0 a cardV-1. */ private int index; /*Nombre del vertice */ private String name; /*Crea un vértice cuyo índice se desconoce.*/ public Vertex(String name) { index = UNKNOWN_INDEX; this.name = name; } /*Crea un vértice cuyo índice y nombre se conoce.*/ public Vertex(int index, String name){ this.index = index; this.name = name; } /*modifica el indice */

30

public void setIndex(int index){ this.index = index; } /* retorna el indice del vertice */ public int getIndex(){ return index; } /*Modifica el nombre de vertice*/ public void setName(String name){ this.name = name; } /*Retorna el nombre del vertice. */ public String getName(){ return name; } /**retorna la representacion del vertice */ public String toString(){ return name + " (index = " + index + ")"; } }

Clase WeigthtedAdjancencyListGraph: package algoritmojohnson; import java.util.Iterator; /* @author Alfredo Parra y Carlos San Juan */ public class WeightedAdjacencyListGraph extends AdjacencyListGraph{ /** cardV:Se recive la cantidad de vertices del Grafo directed: indetificar si el grafo es direccionado o no. */ public WeightedAdjacencyListGraph(int cardV, boolean directed){ super(cardV, directed); } public void addEdge(Vertex u, Vertex v){ //Verifica que los bordes del grafo tengan peso throw new UnsupportedOperationException(); } public void addEdge(int u, int v) { throw new UnsupportedOperationException(); } /**

31

Agrega un margen ponderado de este gráfico. El borde es especificado por un par de vertices "u" un vertice. "v" el otro vertice. "weight" el peso del borde*/ public void addEdge(Vertex u, Vertex v, double weight) { // Ponemos v en u su lista. int uIndex = u.getIndex(); Edge x = new WeightedEdge(v, adj[uIndex].head, weight); adj[uIndex].head = x; // Si no es dirigido ponemos el vertice "u" en la lista de "v" if (!directed) { int vIndex = v.getIndex(); x = new WeightedEdge(u, adj[vIndex].head, weight); adj[vIndex].head = x; } e++; } /*Agrega un margen al grafo. el borde especificado por un par de vertices u indicador del primer vertice. v el indicador del otro vertice weight el valor del arco. */ public void addEdge(int u, int v, double weight) { // Poner v en lista de u Edge x = new WeightedEdge(adj[v].thisVertex, adj[u].head, weight); adj[u].head = x; //si no es dirigido, poner u en lista de v if (!directed) { x = new WeightedEdge(adj[u].thisVertex, adj[v].head, weight); adj[v].head = x; } }

e++;

/*Clase interna de los bordes ponderados en las listas de adyacencia. Listas de adyacencia son simplemente enlazada*/ protected static class WeightedEdge extends Edge{ //el peso del borde private double weight; /**Creamos el nuevo peso * v el vertice adjacente * successor borde sucesor a este * wgt el nuevo peso del borde*/ public WeightedEdge(Vertex v, Edge successor, double wgt){ super(v, successor); weight = wgt; }

32

public void setWeight(double wgt){ weight = wgt; } public double getWeight(){ return weight; } } /** Devuelve un iterador que itera a través de las aristas incidentes ponderada en un vértice dado. Cada arista incidente se indica mediante el correspondiente vértice adyacente. "u" es el vértice cuyo aristas incidentes son devueltos por el iterador*/ public Iterator edgeIterator(Vertex u){ return new EdgeIterator(u.getIndex()); } public Iterator edgeIterator(int u){ return new EdgeIterator(u); } /*Devuelve un iterador, de WeightedEdgeIterator tipo (de modo que la persona que llama no tiene que convertir el resultado), que recorre las aristas incidentes ponderada en un vértice dado. Cada arista incidente se indica mediante el correspondiente vértice adyacente. */ public WeightedEdgeIterator weightedEdgeIterator(Vertex u){ return weightedEdgeIterator(u.getIndex()); } public WeightedEdgeIterator weightedEdgeIterator(int u){ return new EdgeIterator(u); } /*CLASE INTERNA */ public class EdgeIterator extends AdjacencyListGraph.EdgeIterator implements WeightedEdgeIterator{ /*Inicia una iteración a través de las aristas incidentes ponderada en un vértice dado.*/ public EdgeIterator(int v){ super(v); } /*Devuelve el peso de la orilla devuelto por la llamada más reciente a la siguiente*/ public double getWeight(){ return ((WeightedEdge) current).getWeight(); }

}

public void setWeight(double weight){ ((WeightedEdge) current).setWeight(weight); }

33

/*Crea y devuelve una WeightedAdjacencyListGraph vacío, sin bordes, dado el número de vértices y un booleano que indica si el grafo es dirigido.*/ protected AdjacencyListGraph makeEmptyGraph(int cardV, boolean directed) { return new WeightedAdjacencyListGraph(cardV, directed); } /*Devuelve la representacion de un grafo ponderado */ public String toString() { String result = ""; Iterator vertexIter = vertexIterator(); while (vertexIter.hasNext()) { Vertex u = (Vertex) vertexIter.next(); result += u + ":\n"; WeightedEdgeIterator edgeIter = weightedEdgeIterator(u); while (edgeIter.hasNext()) { Vertex v = (Vertex) edgeIter.next(); double w = edgeIter.getWeight(); result += " " + v + ", weight = " + w + "\n"; }

}

} return result;

}

Clase WeightedEdgeIterator: package algoritmojohnson; import java.util.Iterator; /* @author Alfredo Parra y Carlos San Juan */ public interface WeightedEdgeIterator extends Iterator{ /*Devuelve el peso de la orilla devuelto por la llamada más reciente a la siguiente.*/ public double getWeight(); public void setWeight(double weight); }

34

PRUEBAS DEL ALGORITMO Por motivos de espacio, solo realizaremos una prueba para mostrar cómo trabaja nuestro algoritmo, ya que el resultado entregado es un poco extenso, pero el gráfico será con las 5 pruebas que se piden, a continuación los grafos que utilizamos en el programa y la solución de este, además de las 5 pruebas realizadas donde analizaremos el tiempo.

1.-

2.-

4.-

5.-

35

Ejecución de nuestro Algoritmo de Johnson: PRIMER GRAFO: a (index = 0): e (index = 4), weight = -4.0 c (index = 2), weight = 8.0 b (index = 1), weight = 3.0 b (index = 1): d (index = 3), weight = 1.0 e (index = 4), weight = 7.0 c (index = 2): b (index = 1), weight = 4.0 d (index = 3): a (index = 0), weight = 2.0 c (index = 2), weight = -5.0 e (index = 4): d (index = 3), weight = 6.0

**** Uso de Johnson 1 *** Grafo con nodo nuevo 's': a (index = 0): b (index = 1), weight = 3.0 c (index = 2), weight = 8.0 e (index = 4), weight = -4.0 b (index = 1): e (index = 4), weight = 7.0 d (index = 3), weight = 1.0 c (index = 2): b (index = 1), weight = 4.0 d (index = 3): c (index = 2), weight = -5.0 a (index = 0), weight = 2.0 e (index = 4): d (index = 3), weight = 6.0 s (index = 5): e (index = 4), weight = 0.0 d (index = 3), weight = 0.0 c (index = 2), weight = 0.0 b (index = 1), weight = 0.0 a (index = 0), weight = 0.0 Muestra los nuevos pesos h(v) 0.0 -1.0 -5.0 0.0 -4.0 0.0 Grafo con pesos recalculados: w(u, v) + h(u) − h(v) a (index = 0): b (index = 1), weight = 4.0 c (index = 2), weight = 13.0

36

e (index = 4), weight = 0.0 b (index = 1): e (index = 4), weight = 10.0 d (index = 3), weight = 0.0 c (index = 2): b (index = 1), weight = 0.0 d (index = 3): c (index = 2), weight = 0.0 a (index = 0), weight = 2.0 e (index = 4): d (index = 3), weight = 2.0 s (index = 5): e (index = 4), weight = 4.0 d (index = 3), weight = 0.0 c (index = 2), weight = 5.0 b (index = 1), weight = 1.0 a (index = 0), weight = 0.0 Ejecución Dijkstra: Desde: a (index = 0) Recorrido más corto: a->e->d->c->b Hacia: a (index = 0)d = 0.0, pi = (null) Hacia: b (index = 1)d = 1.0, pi = c Hacia: c (index = 2)d = -3.0, pi = d Hacia: d (index = 3)d = 2.0, pi = e Hacia: e (index = 4)d = -4.0, pi = a Desde: b (index = 1) Recorrido mas corto: b->d->c->a->e Hacia: a (index = 0)d = 3.0, pi = d Hacia: b (index = 1)d = 0.0, pi = (null) Hacia: c (index = 2)d = -4.0, pi = d Hacia: d (index = 3)d = 1.0, pi = b Hacia: e (index = 4)d = -1.0, pi = a Desde: c (index = 2) Recorrido mas corto: c->b->d->a->e Hacia: a (index = 0)d = 7.0, pi = d Hacia: b (index = 1)d = 4.0, pi = c Hacia: c (index = 2)d = 0.0, pi = (null) Hacia: d (index = 3)d = 5.0, pi = b Hacia: e (index = 4)d = 3.0, pi = a Desde: d (index = 3) Recorrido más corto: d->c->b->a->e Hacia: a (index = 0)d = 2.0, pi = d Hacia: b (index = 1)d = -1.0, pi = c Hacia: c (index = 2)d = -5.0, pi = d Hacia: d (index = 3)d = 0.0, pi = (null) Hacia: e (index = 4)d = -2.0, pi = a Desde: e (index = 4) Recorrido más corto: e->d->c->b->a Hacia: a (index = 0)d = 8.0, pi = d

37

Hacia: b (index = 1)d = 5.0, pi = c Hacia: c (index = 2)d = 1.0, pi = d Hacia: d (index = 3)d = 6.0, pi = e Hacia: e (index = 4)d = 0.0, pi = (null)

** FIN JOHNSON 1** tiempo de ejecución 1: 73 miliseg

SEGUND GRAFO (1) (index = 0): (2) (index = 1): (3) (index = 2), weight = 2.0 (1) (index = 0), weight = 1.0 (3) (index = 2): (2) (index = 1), weight = 1.0 (1) (index = 0), weight = 4.0 (4) (index = 3): (5) (index = 4), weight = 4.0 (2) (index = 1), weight = 8.0 (5) (index = 4): (4) (index = 3), weight = 2.0 (3) (index = 2), weight = 2.0 **** Uso de Johnson 2*** Grafo con nodo nuevo 's': (1) (index = 0): (2) (index = 1): (1) (index = 0), weight = 1.0 (3) (index = 2), weight = 2.0 (3) (index = 2): (1) (index = 0), weight = 4.0 (2) (index = 1), weight = 1.0 (4) (index = 3): (2) (index = 1), weight = 8.0 (5) (index = 4), weight = 4.0 (5) (index = 4): (3) (index = 2), weight = 2.0 (4) (index = 3), weight = 2.0 s (index = 5): (5) (index = 4), weight = 0.0 (4) (index = 3), weight = 0.0 (3) (index = 2), weight = 0.0 (2) (index = 1), weight = 0.0 (1) (index = 0), weight = 0.0 Muestra los nuevos pesos h(v) 0.0 0.0

38

0.0 0.0 0.0 0.0 Grafo con pesos recalculados: w(u, v) + h(u) − h(v) (1) (index = 0): (2) (index = 1): (1) (index = 0), weight = 1.0 (3) (index = 2), weight = 2.0 (3) (index = 2): (1) (index = 0), weight = 4.0 (2) (index = 1), weight = 1.0 (4) (index = 3): (2) (index = 1), weight = 8.0 (5) (index = 4), weight = 4.0 (5) (index = 4): (3) (index = 2), weight = 2.0 (4) (index = 3), weight = 2.0 s (index = 5): (5) (index = 4), weight = 0.0 (4) (index = 3), weight = 0.0 (3) (index = 2), weight = 0.0 (2) (index = 1), weight = 0.0 (1) (index = 0), weight = 0.0 Ejecución Dijkstra: Desde: (1) (index = 0) Recorrido más corto: (1)->s->(5)->(4)->(3) Hacia: (1) (index = 0)d = 0.0, pi = (null) Hacia: (2) (index = 1)d = Infinity, pi = (null) Hacia: (3) (index = 2)d = Infinity, pi = (null) Hacia: (4) (index = 3)d = Infinity, pi = (null) Hacia: (5) (index = 4)d = Infinity, pi = (null) Desde: (2) (index = 1) Recorrido más corto: (2)->(1)->(3)->(4)->(5) Hacia: (1) (index = 0)d = 1.0, pi = (2) Hacia: (2) (index = 1)d = 0.0, pi = (null) Hacia: (3) (index = 2)d = 2.0, pi = (2) Hacia: (4) (index = 3)d = Infinity, pi = (null) Hacia: (5) (index = 4)d = Infinity, pi = (null) Desde: (3) (index = 2) Recorrido más corto: (3)->(2)->(1)->(4)->s Hacia: (1) (index = 0)d = 2.0, pi = (2) Hacia: (2) (index = 1)d = 1.0, pi = (3) Hacia: (3) (index = 2)d = 0.0, pi = (null) Hacia: (4) (index = 3)d = Infinity, pi = (null) Hacia: (5) (index = 4)d = Infinity, pi = (null) Desde: (4) (index = 3) Recorrido más corto: (4)->(5)->(3)->(2)->(1) Hacia: (1) (index = 0)d = 8.0, pi = (2)

39

Hacia: (2) (index = 1)d = 7.0, pi = (3) Hacia: (3) (index = 2)d = 6.0, pi = (5) Hacia: (4) (index = 3)d = 0.0, pi = (null) Hacia: (5) (index = 4)d = 4.0, pi = (4) Desde: (5) (index = 4) Recorrido más corto: (5)->(3)->(4)->(2)->(1) Hacia: (1) (index = 0)d = 4.0, pi = (2) Hacia: (2) (index = 1)d = 3.0, pi = (3) Hacia: (3) (index = 2)d = 2.0, pi = (5) Hacia: (4) (index = 3)d = 2.0, pi = (5) Hacia: (5) (index = 4)d = 0.0, pi = (null)

** FIN JOHNSON 2** Tiempo de ejecución 2: 28 miliseg

TERCERA PRUEBA (0) (index = 0): (2) (index = 2), weight = 13.0 (1) (index = 1), weight = 16.0 (1) (index = 1): (3) (index = 3), weight = 12.0 (2) (index = 2), weight = 10.0 (2) (index = 2): (4) (index = 4), weight = 14.0 (1) (index = 1), weight = 4.0 (3) (index = 3): (5) (index = 5), weight = 20.0 (2) (index = 2), weight = 9.0 (4) (index = 4): (5) (index = 5), weight = 4.0 (3) (index = 3), weight = 7.0 (5) (index = 5):

**** Uso de Johnson 3 *** Grafo con nodo nuevo 's': (0) (index = 0): (1) (index = 1), weight = 16.0 (2) (index = 2), weight = 13.0 (1) (index = 1): (2) (index = 2), weight = 10.0 (3) (index = 3), weight = 12.0 (2) (index = 2): (1) (index = 1), weight = 4.0 (4) (index = 4), weight = 14.0 (3) (index = 3): (2) (index = 2), weight = 9.0 (5) (index = 5), weight = 20.0

40

(4) (index = 4): (3) (index = 3), weight = 7.0 (5) (index = 5), weight = 4.0 (5) (index = 5): s (index = 6): (5) (index = 5), weight = 0.0 (4) (index = 4), weight = 0.0 (3) (index = 3), weight = 0.0 (2) (index = 2), weight = 0.0 (1) (index = 1), weight = 0.0 (0) (index = 0), weight = 0.0 Muestra los nuevos pesos h(v) 0.0 0.0 0.0 0.0 0.0 0.0 0.0 Grafo con pesos recalculados: w(u, v) + h(u) − h(v) (0) (index = 0): (1) (index = 1), weight = 16.0 (2) (index = 2), weight = 13.0 (1) (index = 1): (2) (index = 2), weight = 10.0 (3) (index = 3), weight = 12.0 (2) (index = 2): (1) (index = 1), weight = 4.0 (4) (index = 4), weight = 14.0 (3) (index = 3): (2) (index = 2), weight = 9.0 (5) (index = 5), weight = 20.0 (4) (index = 4): (3) (index = 3), weight = 7.0 (5) (index = 5), weight = 4.0 (5) (index = 5): s (index = 6): (5) (index = 5), weight = 0.0 (4) (index = 4), weight = 0.0 (3) (index = 3), weight = 0.0 (2) (index = 2), weight = 0.0 (1) (index = 1), weight = 0.0 (0) (index = 0), weight = 0.0 Execution Dijkstra: Desde: (0) (index = 0) Recorrido más corto: (0)->(2)->(1)->(4)->(3)->(5) Hacia: (0) (index = 0)d = 0.0, pi = (null) Hacia: (1) (index = 1)d = 16.0, pi = (0) Hacia: (2) (index = 2)d = 13.0, pi = (0) Hacia: (3) (index = 3)d = 28.0, pi = (1)

41

Hacia: (4) (index = 4)d = 27.0, pi = (2) Hacia: (5) (index = 5)d = 31.0, pi = (4) Desde: (1) (index = 1) Recorrido más corto: (1)->(2)->(3)->(4)->(5)->s Hacia: (0) (index = 0)d = Infinity, pi = (null) Hacia: (1) (index = 1)d = 0.0, pi = (null) Hacia: (2) (index = 2)d = 10.0, pi = (1) Hacia: (3) (index = 3)d = 12.0, pi = (1) Hacia: (4) (index = 4)d = 24.0, pi = (2) Hacia: (5) (index = 5)d = 28.0, pi = (4) Desde: (2) (index = 2) Recorrido más corto: (2)->(1)->(4)->(3)->(5)->(0) Hacia: (0) (index = 0)d = Infinity, pi = (null) Hacia: (1) (index = 1)d = 4.0, pi = (2) Hacia: (2) (index = 2)d = 0.0, pi = (null) Hacia: (3) (index = 3)d = 16.0, pi = (1) Hacia: (4) (index = 4)d = 14.0, pi = (2) Hacia: (5) (index = 5)d = 18.0, pi = (4) Desde: (3) (index = 3) Recorrido más corto: (3)->(2)->(1)->(5)->(4)->s Hacia: (0) (index = 0)d = Infinity, pi = (null) Hacia: (1) (index = 1)d = 13.0, pi = (2) Hacia: (2) (index = 2)d = 9.0, pi = (3) Hacia: (3) (index = 3)d = 0.0, pi = (null) Hacia: (4) (index = 4)d = 23.0, pi = (2) Hacia: (5) (index = 5)d = 20.0, pi = (3) Desde: (4) (index = 4) Recorrido más corto: (4)->(5)->(3)->(2)->(1)->(0) Hacia: (0) (index = 0)d = Infinity, pi = (null) Hacia: (1) (index = 1)d = 20.0, pi = (2) Hacia: (2) (index = 2)d = 16.0, pi = (3) Hacia: (3) (index = 3)d = 7.0, pi = (4) Hacia: (4) (index = 4)d = 0.0, pi = (null) Hacia: (5) (index = 5)d = 4.0, pi = (4) Desde: (5) (index = 5) Recorrido más corto: (5)->s->(2)->(4)->(3)->(0) Hacia: (0) (index = 0)d = Infinity, pi = (null) Hacia: (1) (index = 1)d = Infinity, pi = (null) Hacia: (2) (index = 2)d = Infinity, pi = (null) Hacia: (3) (index = 3)d = Infinity, pi = (null) Hacia: (4) (index = 4)d = Infinity, pi = (null) Hacia: (5) (index = 5)d = 0.0, pi = (null) d = 20.0, pi = (2) ** FIN JOHNSON 3** tiempo de ejecución grafo 3: 33 miliseg

CUARTA PRUEBA (0) (index = 0):

42

(2) (index = 2), weight = 13.0 (1) (index = 1), weight = 16.0 (1) (index = 1): (3) (index = 3), weight = 12.0 (2) (index = 2), weight = 10.0 (2) (index = 2): (4) (index = 4), weight = 14.0 (1) (index = 1), weight = 4.0 (3) (index = 3): (5) (index = 5), weight = 20.0 (2) (index = 2), weight = 9.0 (4) (index = 4): (5) (index = 5), weight = 4.0 (3) (index = 3), weight = 7.0 (5) (index = 5):

**** Uso de Johnson 4*** Grafo con nodo nuevo 's': (W) (index = 0): (Z) (index = 3), weight = 2.0 (X) (index = 1): (Y) (index = 2), weight = 3.0 (W) (index = 0), weight = 6.0 (Y) (index = 2): (W) (index = 0), weight = 4.0 (Z) (index = 3), weight = 5.0 (Z) (index = 3): (Y) (index = 2), weight = 3.0 (X) (index = 1), weight = -7.0 s (index = 4): (Z) (index = 3), weight = 0.0 (Y) (index = 2), weight = 0.0 (X) (index = 1), weight = 0.0 (W) (index = 0), weight = 0.0 Muestra los nuevos pesos h(v) -1.0 -7.0 -4.0 0.0 0.0 Grafo con pesos recalculados: w(u, v) + h(u) − h(v) (W) (index = 0): (Z) (index = 3), weight = 1.0 (X) (index = 1): (Y) (index = 2), weight = 0.0 (W) (index = 0), weight = 0.0 (Y) (index = 2): (W) (index = 0), weight = 1.0 (Z) (index = 3), weight = 1.0 (Z) (index = 3): (Y) (index = 2), weight = 7.0

43

(X) (index = 1), weight = 0.0 s (index = 4): (Z) (index = 3), weight = 0.0 (Y) (index = 2), weight = 4.0 (X) (index = 1), weight = 7.0 (W) (index = 0), weight = 1.0 Ejecución Dijkstra: Desde: (W) (index = 0) Recorrido más corto: (W)->(Z)->(X)->(Y) Hacia: (W) (index = 0)d = 0.0, pi = (null) Hacia: (X) (index = 1)d = -5.0, pi = (Z) Hacia: (Y) (index = 2)d = -2.0, pi = (X) Hacia: (Z) (index = 3)d = 2.0, pi = (W) Desde: (X) (index = 1) Recorrido más corto: (X)->(Y)->(W)->(Z) Hacia: (W) (index = 0)d = 6.0, pi = (X) Hacia: (X) (index = 1)d = 0.0, pi = (null) Hacia: (Y) (index = 2)d = 3.0, pi = (X) Hacia: (Z) (index = 3)d = 8.0, pi = (Y) Desde: (Y) (index = 2) Recorrido más corto: (Y)->(W)->(Z)->(X) Hacia: (W) (index = 0)d = 4.0, pi = (Y) Hacia: (X) (index = 1)d = -2.0, pi = (Z) Hacia: (Y) (index = 2)d = 0.0, pi = (null) Hacia: (Z) (index = 3)d = 5.0, pi = (Y) Desde: (Z) (index = 3) Recorrido más corto: (Z)->(X)->(Y)->(W) Hacia: (W) (index = 0)d = -1.0, pi = (X) Hacia: (X) (index = 1)d = -7.0, pi = (Z) Hacia: (Y) (index = 2)d = -4.0, pi = (X) Hacia: (Z) (index = 3)d = 0.0, pi = (null)

** FIN JOHNSON 4** tiempo de ejecución 4: 21 miliseg

QUINTA PRUEBA (A) (index = 0): (E) (index = 4), weight = 2.0 (B) (index = 1): (C) (index = 2), weight = 1.0 (A) (index = 0), weight = 1.0 (C) (index = 2): (D) (index = 3), weight = 3.0 (D) (index = 3): (E) (index = 4), weight = -1.0

44

(E) (index = 4): (B) (index = 1), weight = -2.0 (F) (index = 5): (E) (index = 4), weight = -1.0 (A) (index = 0), weight = -4.0 (G) (index = 6): (F) (index = 5), weight = 1.0 (H) (index = 7): (G) (index = 6), weight = 1.0 (A) (index = 0), weight = 10.0

**** Uso de Johnson 5 *** Grafo con nodo nuevo 's': (A) (index = 0): (E) (index = 4), weight = 2.0 (B) (index = 1): (A) (index = 0), weight = 1.0 (C) (index = 2), weight = 1.0 (C) (index = 2): (D) (index = 3), weight = 3.0 (D) (index = 3): (E) (index = 4), weight = -1.0 (E) (index = 4): (B) (index = 1), weight = -2.0 (F) (index = 5): (A) (index = 0), weight = -4.0 (E) (index = 4), weight = -1.0 (G) (index = 6): (F) (index = 5), weight = 1.0 (H) (index = 7): (A) (index = 0), weight = 10.0 (G) (index = 6), weight = 1.0 s (index = 8): (H) (index = 7), weight = 0.0 (G) (index = 6), weight = 0.0 (F) (index = 5), weight = 0.0 (E) (index = 4), weight = 0.0 (D) (index = 3), weight = 0.0 (C) (index = 2), weight = 0.0 (B) (index = 1), weight = 0.0 (A) (index = 0), weight = 0.0 Muestra los nuevos pesos h(v) -4.0 -4.0 -3.0 0.0 -2.0 0.0 0.0 0.0 0.0 Grafo con pesos recalculados: w(u, v) + h(u) − h(v)

45

(A) (index = 0): (E) (index = 4), weight = 0.0 (B) (index = 1): (A) (index = 0), weight = 1.0 (C) (index = 2), weight = 0.0 (C) (index = 2): (D) (index = 3), weight = 0.0 (D) (index = 3): (E) (index = 4), weight = 1.0 (E) (index = 4): (B) (index = 1), weight = 0.0 (F) (index = 5): (A) (index = 0), weight = 0.0 (E) (index = 4), weight = 1.0 (G) (index = 6): (F) (index = 5), weight = 1.0 (H) (index = 7): (A) (index = 0), weight = 14.0 (G) (index = 6), weight = 1.0 s (index = 8): (H) (index = 7), weight = 0.0 (G) (index = 6), weight = 0.0 (F) (index = 5), weight = 0.0 (E) (index = 4), weight = 2.0 (D) (index = 3), weight = 0.0 (C) (index = 2), weight = 3.0 (B) (index = 1), weight = 4.0 (A) (index = 0), weight = 4.0 Ejecución Dijkstra: Desde: (A) (index = 0) Recorrido más corto: (A)->(E)->(B)->(C)->(D)->s->(H)->(G) Hacia: (A) (index = 0)d = 0.0, pi = (null) Hacia: (B) (index = 1)d = 0.0, pi = (E) Hacia: (C) (index = 2)d = 1.0, pi = (B) Hacia: (D) (index = 3)d = 4.0, pi = (C) Hacia: (E) (index = 4)d = 2.0, pi = (A) Hacia: (F) (index = 5)d = Infinity, pi = (null) Hacia: (G) (index = 6)d = Infinity, pi = (null) Hacia: (H) (index = 7)d = Infinity, pi = (null) Desde: (B) (index = 1) Recorrido más corto: (B)->(C)->(D)->(A)->(E)->(G)->s->(H) Hacia: (A) (index = 0)d = 1.0, pi = (B) Hacia: (B) (index = 1)d = 0.0, pi = (null) Hacia: (C) (index = 2)d = 1.0, pi = (B) Hacia: (D) (index = 3)d = 4.0, pi = (C) Hacia: (E) (index = 4)d = 3.0, pi = (D) Hacia: (F) (index = 5)d = Infinity, pi = (null) Hacia: (G) (index = 6)d = Infinity, pi = (null) Hacia: (H) (index = 7)d = Infinity, pi = (null) Desde: (C) (index = 2) Recorrido más corto: (C)->(D)->(E)->(B)->(A)->s->(H)->(F)

46

Hacia: (A) (index = 0)d = 1.0, pi = (B) Hacia: (B) (index = 1)d = 0.0, pi = (E) Hacia: (C) (index = 2)d = 0.0, pi = (null) Hacia: (D) (index = 3)d = 3.0, pi = (C) Hacia: (E) (index = 4)d = 2.0, pi = (D) Hacia: (F) (index = 5)d = Infinity, pi = (null) Hacia: (G) (index = 6)d = Infinity, pi = (null) Hacia: (H) (index = 7)d = Infinity, pi = (null) Desde: (D) (index = 3) Recorrido más corto: (D)->(E)->(B)->(C)->(A)->(H)->s->(F) Hacia: (A) (index = 0)d = -2.0, pi = (B) Hacia: (B) (index = 1)d = -3.0, pi = (E) Hacia: (C) (index = 2)d = -2.0, pi = (B) Hacia: (D) (index = 3)d = 0.0, pi = (null) Hacia: (E) (index = 4)d = -1.0, pi = (D) Hacia: (F) (index = 5)d = Infinity, pi = (null) Hacia: (G) (index = 6)d = Infinity, pi = (null) Hacia: (H) (index = 7)d = Infinity, pi = (null) Desde: (E) (index = 4) Recorrido más corto: (E)->(B)->(C)->(D)->(A)->s->(H)->(G) Hacia: (A) (index = 0)d = -1.0, pi = (B) Hacia: (B) (index = 1)d = -2.0, pi = (E) Hacia: (C) (index = 2)d = -1.0, pi = (B) Hacia: (D) (index = 3)d = 2.0, pi = (C) Hacia: (E) (index = 4)d = 0.0, pi = (null) Hacia: (F) (index = 5)d = Infinity, pi = (null) Hacia: (G) (index = 6)d = Infinity, pi = (null) Hacia: (H) (index = 7)d = Infinity, pi = (null) Desde: (F) (index = 5) Recorrido más corto: (F)->(A)->(E)->(B)->(C)->(D)->(G)->s Hacia: (A) (index = 0)d = -4.0, pi = (F) Hacia: (B) (index = 1)d = -4.0, pi = (E) Hacia: (C) (index = 2)d = -3.0, pi = (B) Hacia: (D) (index = 3)d = 0.0, pi = (C) Hacia: (E) (index = 4)d = -2.0, pi = (A) Hacia: (F) (index = 5)d = 0.0, pi = (null) Hacia: (G) (index = 6)d = Infinity, pi = (null) Hacia: (H) (index = 7)d = Infinity, pi = (null) Desde: (G) (index = 6) Recorrido más corto: (G)->(F)->(A)->(E)->(B)->(C)->(D)->(H) Hacia: (A) (index = 0)d = -3.0, pi = (F) Hacia: (B) (index = 1)d = -3.0, pi = (E) Hacia: (C) (index = 2)d = -2.0, pi = (B) Hacia: (D) (index = 3)d = 1.0, pi = (C) Hacia: (E) (index = 4)d = -1.0, pi = (A) Hacia: (F) (index = 5)d = 1.0, pi = (G) Hacia: (G) (index = 6)d = 0.0, pi = (null) Hacia: (H) (index = 7)d = Infinity, pi = (null) Desde: (H) (index = 7) Recorrido más corto: (H)->(G)->(F)->(A)->(E)->(B)->(C)->(D)

47

Hacia: (A) (index = 0)d = -2.0, pi = (F) Hacia: (B) (index = 1)d = -2.0, pi = (E) Hacia: (C) (index = 2)d = -1.0, pi = (B) Hacia: (D) (index = 3)d = 2.0, pi = (C) Hacia: (E) (index = 4)d = 0.0, pi = (A) Hacia: (F) (index = 5)d = 2.0, pi = (G) Hacia: (G) (index = 6)d = 1.0, pi = (H) Hacia: (H) (index = 7)d = 0.0, pi = (null)

** FIN JOHNSON 5** tiempo de ejecución 5: 26 miliseg

Resultados de las ejecuciones: miliseg

Grafo 1

Grafo 2

Grafo 3

Grafo 4

Grafo 5

t1

73

28

33

21

26

t2

76

14

33

26

49

t3

74

21

25

34

32

t4

67

30

22

18

69

t5

104

34

43

13

51

120 105 90 75 60 45 30 15 0 t1

t2 Grafo 1

Grafo 2

t3 Grafo 3

t4 Grafo 4

t5 Grafo 5

48

Análisis del Algoritmo: 𝑷𝒂𝒓𝒂 𝒈𝒓𝒂𝒇𝒐𝒔 𝒔𝒆 𝒖𝒔𝒂 𝒍𝒂 𝒎𝒂𝒚𝒐𝒓𝒊𝒕𝒂𝒓𝒊𝒂𝒎𝒆𝒏𝒕𝒆 𝒆𝒔𝒕𝒂 𝒔𝒊𝒎𝒃𝒐𝒍𝒐𝒈í𝒂: 𝑮𝒓𝒂𝒇𝒐 = 𝑮, 𝑽𝒆𝒓𝒕𝒊𝒄𝒆𝒔 = 𝑽, 𝑩𝒐𝒓𝒅𝒆𝒔 = 𝑬 (𝑬𝒅𝒈𝒆) Se busca encontrar el camino más corto entre todos los pares en ( ) . Para grafos dispersos, es asintóticamente más rápido que sea repetido la cuadratura del matrices o el algoritmo de Floyd-Warshall. El algoritmo o bien devuelve una matriz de la ruta más corta de pesos para todos los pares de vértices o informes que el grafo de entrada contiene un ciclo negativo de peso. Algoritmo de Johnson utiliza como subrutinas, tanto Dijkstra y el algoritmo de Bellman-Ford. Algoritmo de Johnson utiliza la técnica de ponderación, que funciona usando todos los pesos de las aristas en una grafo = ( , ) son positivos, podemos encontrar más corto rutas entre todos los pares de vértices mediante la ejecución de algoritmo de Dijkstra, una vez de cada vértice, con el Heap-Fibonacci y la cola de min-prioridad, el tiempo de ejecución de este todos los pares de algoritmo es ( ) Si tiene pesos negativos en los bordes, pero no ciclos negativos, simplemente se calcula un nuevo conjunto de pesos para las aristas no negativas, que nos permite utilizar el mismo método. El nuevo conjunto de pesos de las aristas y debe satisfacer dos propiedades importantes: 1. Para todos los pares de vértices , , un camino es un camino más corto usado desde para utilizando la función de peso si y sólo si es también un camino más corto desde hasta utilizando la función de peso . 2. Para todos los bordes ( , ), el nuevo peso y

( , ) no es negativo.

En nuestro grafo numero 1 ( ( , ), = , = ) vemos que hay bordes con pesos negativos, por lo tanto lo primero que debe hacer nuestro algoritmo es verificar que ni existan ciclos negativos para luego crear un vértice nuevo para poder redirigirse al resto de los vértices y usar el algoritmo de Bellman-Ford donde ( ) se calcula ( , ), para así poder cambiar los pesos de las aristas. Una vez realizados los cambios teniendo un grafo al cual se le puede aplicar Dijkstra al vértice 1, ( , ) ( , ), para obtener los caminos más cortos. Si calculamos tendríamos: ( )= ( ) ( , )= = ( ) ( ) ( ) ( ) = , = = Aplicamos Dijkstra al vértice 2, al vértice 3, al vértice 4 y al 5 y termina la aplicación del algoritmo de Johnson.

49

Conclusión Al desarrollar este algoritmo nos hemos dado cuenta de lo importante que son los grafos y la gran incidencia que tienen en nuestra vida cotidiana y laboral, ya que en la búsqueda de ejemplos vimos los muchos usos que se les dan. Eso en términos globales, pero si nos enfocamos más en el problema podemos deducir varias cosas interesantes, entre ellas los diferentes tiempos que se demora un programa para resolver un mismo algoritmo, si bien son escazas diferencias, nos enseñan que la computación no es exacta como las matemáticas, si bien se pueden estimar los tiempos mediante fórmulas y cálculos, hay varias cosas que pueden influir. Por ejemplo el procesador del computador, ya que los tiempos varían de un computado a otro. Por otra parte descubrimos un nuevo algoritmo, que no habíamos escuchado anteriormente y que gracias a este pudimos introducirnos en otros dos grandes algoritmos como lo son el Dijkstra y el algoritmo de Bellman-Ford, los funcionamientos de esto y como juntos resuelven más problemas. Para finalizar podemos decir que el algoritmo de Johnson es muy útil ya que resuelve una parte importante de grafos complicados y que para nosotros es fundamental tener una herramienta como esta.

50