Algoritmo de Dijkstra
Dijkstra y Prim
Nombre: Jesús Muñoz -
Maximiliano Quinteros
Sección: 94
PUNTOS A TRATAR:
Descripción de la problemática aabordar
Descripción de las partes más complejas de resolver
Identificación de limitaciones de la solución entregada
Conclusiones
DESCRIPCION:
Utilizando ellenguaje de programación Visual Basic 2010 procederemos a construir los dos algoritmos que determinaran el camino más corto de un vértice a otro. El algoritmo de Dijkstra es el que nos permitirá conocer elcamino más corto entre vértices y el algoritmo de Prim que dará salida de un vértice a todos los vértices restantes encontrando así el camino más corto entre estos. Nuestro proyecto consta de 10vértices a abordar como lo muestra la imagen a continuación.
MATRIZ DE ADYACENCIA:
El software comienza con la creación de una matriz de adyacencia simple que se crea al mismo tiempo dedibujar o crear un vértice, para realizar esto se necesitó utilizar un array multidimensional para los valores asignados en las aristas. (Ejemplo en la imagen)
CAMINO MAS CORTO DIJKSTRA:Para resolver el camino más corto, se utilizó el algoritmo de Dijkstra que toma el vértice inicial y compara con que vértices está unido, esto se hace con un ciclo. Luego toma el peso menor de unvértice con otro, lo guarda y hace el mismo ciclo nuevamente hasta el final. (Observación: a todas las aristas se le dio un valor de 1)
PRIM:
Para resolver este algoritmo era necesario tenerprogramado el algoritmo de Dijkstra se tomó en cuenta el punto de donde comienza el recorrido, y verificando cual es el menor peso que tienen los vértices de al lado hasta recorrer todos los vértices.DIFICULTADES DEL PROYECTO:
El paso más complejo de hacer fue Realizar el recorrido para el algoritmo de dijsktra, para ello tuvimos que crear un array multidimensional...
Regístrate para leer el documento completo.