El algoritmo de Dijkstra sin duda es el más popular entre los algoritmos de caminos mínimos en un grafo. Este algoritmo se enfrenta a un problema complejo. La complejidad del problema radica en el tamaño del espacio de búsqueda.

Ciertamente los grafos son de las estructuras de datos que tienden a hacer explotar combinatoriamente la complejidad de los algoritmos que intentan trabajar sobre ellos. Con una cantidad creciente de nodos, los problemas de grafos tienden rápidamente a ser intratables

Algoritmo básico: Calcula la longitud del camino mínimo desde el nodo especificado hasta todos los demás nodos.

Dijkstra(Nodo root) {

	if (!root.hasChildren()) {
		return;
	}
	else {
		for (Edge e : root.getEdges()) {
			int dist = root.getTotalDistance() + e.getDistance();
			if (e.getTargetNode().getTotalDistance() > dist) {
				e.getTargetNode().setTotalDistance(dist);
			}
		}
	}
}

This entry was posted on Thursday, November 3rd, 2005 at 11:21 pm and is filed under algoritmos. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.