El camino más corto:
En grafos para encontrar la ruta o camino mas corto, este consiste en ver los caminos posibles entre dos vértices (nodos) y encontrar el camino que sea pequeño.
1- Algoritmo de Floyd-Warshall:
Es un algoritmo de análisis que busca el camino mas corto entre grafos.
El cual permite calcular la distancia mínima entre dos puntos de un grafo, mediante un proceso iterativo se le asignara a cada nodo Xi un valor n igual a la longitud del camino más corto que exista desde el nodo origen al nodo Xj.
2- Algoritmo Dijkstra:
Este algoritmo se basa en ver y determinar el camino más corto, que parten desde el vértice o nodo de origen y lleva a los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene.
A lo ancho:
Se trata de recorrer un árbol por niveles, que se trata de ubicar el nodo principal para después pasar por los nodos adyacentes al nodo principal, va por los niveles hasta acabar con los niveles del árbol.
Este consta de tres elementos:
-Contador (n)
-Vector de naturales (R) para "marcar" los vértices ya visitados y almacenar el orden del recorrido
- Cola(Q) para almacenar los vértices no visitados
En profundidad:
Algoritmo de recorrido en profundidad o DFS, explora sistemáticamente las aristas de un grafo, que primero se visitan los nodos o vértices adyacentes a los que ya fueron visitados recientemente, de esa forma se profundiza dentro del grafo, alejándose del nodo principal, donde se elije el nodo de partida y se marca como visitado, donde se comienza a visitar a los adyacentes e igual se marcan como visitados, este recorrido puede ser para grafos dirigidos y no dirigidos
No hay comentarios:
Publicar un comentario