Esta pregunta es malformada y extraña. Se trata más de una cuestión de computación paralela o concurrente y no de análisis de algoritmos en el sentido tradicional. El modelo de RAM, por ejemplo, no tiene “hilos”.
Creo que lo que realmente estás preguntando es si ejecutaste el algoritmo de Dijkstra donde exploras desde los dos vértices proporcionados al mismo tiempo. La respuesta es no, no mejorará los asintóticos, ya que si cuenta el número de vértices y bordes marcados, sigue siendo el mismo que Bohdan declaró, ya que dos hilos dejarían un factor constante reducido. Además, el Algoritmo de Dijkstra no tiene sentido realmente en esta configuración, ya que depende del vértice inicial cuando actualiza las distancias (cuando se realiza la relajación del borde). El algoritmo de Dijkstra comienza en un vértice y explora desde dicho vértice. El algoritmo en sí mismo hace crecer un árbol de rutas más cortas (y funciona de manera muy similar a la búsqueda de amplitud primero, pero recuerde que BFS solo está explorando, no tratando de encontrar rutas más cortas desde el vértice inicial) desde el vértice inicial hasta cualquier otro vértice. Entonces, si tuviera que tomar este algoritmo e intentar aplicarlo a más de un “hilo”, podría tener problemas con las ideas del algoritmo de Dijkstra de inmediato ya que el algoritmo en sí no está diseñado para cultivar bosques, su corrección proviene de cultivar un árbol de caminos más cortos (1 árbol) a partir de uno de los vértices elegidos. El segundo vértice técnicamente no podrá hacer nada bajo el algoritmo de Dijkstra hasta que el primer vértice lo visite. Este es un problema común en realidad cuando las personas consideran algoritmos de paralelización como estos, el Algoritmo de Dijkstra no se extiende naturalmente a una configuración distribuida.
Ahora, si quisiera generalizar esto a una configuración más paralela, personalmente me adaptaría para usar Bellman-Ford y no Dijkstra con esta idea, ya que Bellman-Ford tiene mucho sentido en una configuración distribuida. Tenga un hilo para cada vértice (o en la configuración distribuida, cada vértice es una máquina). Sugeriría explorar Bellman-Ford cuando se coloca en la configuración de computación distribuida o paralela. Es muy natural extenderse a la idea que tiene, ya que la relajación solo depende de sí misma y de sus vecinos (y tiene la propiedad que desea).
- ¿Cuál es la estrategia de divide y vencerás? Escribe un algoritmo para encontrar x a la enésima potencia usando el método de dividir y conquistar.
- ¿Por qué el algoritmo ikj es más rápido que el algoritmo ijk para la multiplicación de matrices?
- Si tengo un buen conocimiento de Java, C ++, algoritmos y estructuras de datos y quiero ser un profesional independiente. ¿Cuánto puede ganar alguien con estas habilidades?
- ¿Qué es un algoritmo recursivo (pseudocódigo) que calcula la suma de los primeros enteros positivos impares?
- CodeChef: ¿Está bien resolver los desafíos de programación sin el conocimiento de algoritmos?
¡Espero que esto ayude!
