CodeGym /Corsi /Python SELF IT /Algoritmi di ricerca del percorso più breve

Algoritmi di ricerca del percorso più breve

Python SELF IT
Livello 56, Lezione 3
Disponibile

9.1 Principi di funzionamento dell'algoritmo di Dijkstra

L'algoritmo di Dijkstra è un algoritmo per trovare i percorsi più brevi dal nodo iniziale a tutti gli altri nodi in un grafo con pesi non negativi sugli archi. L'algoritmo utilizza un approccio greedy, scegliendo a ogni passo il nodo con la distanza più piccola nota dal nodo iniziale e aggiornando le distanze ai nodi adiacenti.

Fasi dell'algoritmo:

1. Inizializzazione:

  • Impostiamo la distanza al nodo iniziale pari a 0.
  • Impostiamo la distanza a tutti gli altri nodi pari all'infinito.
  • Creiamo un insieme di nodi non visitati.

2. Scelta del nodo corrente:

  • Scegliamo un nodo non visitato con la distanza più piccola (il nodo iniziale al primo passo).

3. Aggiornamento delle distanze:

  • Per ogni nodo adiacente a quello corrente, se il nuovo percorso attraverso il nodo corrente è più corto del percorso noto, aggiorniamo la distanza a quel nodo.

4. Segniamo il nodo corrente come visitato:

  • Rimuoviamo il nodo corrente dall'insieme dei nodi non visitati.

5. Ripetiamo i passi 2-4, fino a quando non vengono visitati tutti i nodi o non raggiungiamo il nodo di destinazione.

Complessità temporale e spaziale dell'algoritmo di Dijkstra:

Complessità temporale:

O((V + E) log V) quando si utilizza una coda con priorità (per esempio, un heap di Fibonacci), dove V è il numero di nodi, E è il numero di archi.

O(V^2) quando si utilizza una lista semplice per memorizzare le distanze.

Complessità spaziale:

O(V) per memorizzare le distanze e i predecessori (per ricostruire il percorso).

9.2 Implementazione dell'algoritmo di Dijkstra

L'implementazione dell'algoritmo di Dijkstra è lunga, ma molto semplice. Ti consiglio di provare a capirla. Se non è chiaro, torna indietro e rileggi i passaggi principali dell'algoritmo.

Ecco un esempio di implementazione dell'algoritmo di Dijkstra utilizzando una coda di priorità (heap):


import heapq

def dijkstra(graph, start):
    # Inizializzazione
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    parents = {vertex: None for vertex in graph}
            
    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)
            
        # Se la distanza attuale è maggiore di quella registrata, saltiamo il nodo
        if current_distance > distances[current_vertex]:
            continue
            
        # Aggiornamento delle distanze ai nodi adiacenti
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            
            # Se viene trovato un percorso più breve al nodo adiacente
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                parents[neighbor] = current_vertex
                heapq.heappush(priority_queue, (distance, neighbor))
            
    return distances, parents
            
# Esempio di utilizzo:
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
start_vertex = 'A'
distances, parents = dijkstra(graph, start_vertex)
print("Distanze più brevi dal nodo iniziale:", distances)
print("Predecessori per il recupero del percorso:", parents)

Output:


Distanze più brevi dal nodo iniziale: {'A': 0, 'B': 1, 'C': 3, 'D': 4}
Predecessori per il recupero del percorso: {'A': None, 'B': 'A', 'C': 'B', 'D': 'C'}

9.3 Esempi di problemi risolti con l'algoritmo di Dijkstra

Esempi classici di problemi risolti con l'algoritmo di Dijkstra:

1. Ottimizzazione dei percorsi nelle reti di trasporto

Trovare il percorso più breve tra punti in una rete di trasporto (ad esempio, tra città).

Applicazione:

Sistemi di navigazione, come Google Maps, utilizzano l'algoritmo di Dijkstra per calcolare i percorsi ottimali.

2. Pianificazione dei percorsi di consegna

Ottimizzazione dei percorsi per i servizi di consegna di merci, al fine di ridurre i costi e il tempo di consegna.

Applicazione:

Le aziende di logistica utilizzano l'algoritmo di Dijkstra per la pianificazione dei percorsi di consegna e la riduzione dei costi operativi.

3. Gestione delle reti

Ottimizzazione dell'instradamento dei pacchetti di dati nelle reti informatiche per minimizzare i ritardi e aumentare la capacità.

Applicazione:

I protocolli di routing, come OSPF (Open Shortest Path First), utilizzano l'algoritmo di Dijkstra per trovare i percorsi più brevi nelle reti.

4. Analisi delle reti sociali

Trovare percorsi più brevi e misurare la centralità nei grafi sociali (ad esempio, per trovare gli utenti più influenti).

Applicazione:

Le piattaforme social analizzano le connessioni tra gli utenti per fornire raccomandazioni e analizzare l'attività di rete.

5. Giochi e mondi virtuali

Trovare il percorso per i personaggi nei mondi di gioco con ostacoli e diversi livelli di difficoltà.

Applicazione:

I motori di gioco utilizzano l'algoritmo di Dijkstra per calcolare i movimenti di personaggi e oggetti nei mondi virtuali.

6. Sistemi di gestione dell'energia

Ottimizzazione della distribuzione dell'energia nelle reti elettriche per minimizzare le perdite e garantire l'affidabilità delle forniture.

Applicazione:

Le aziende elettriche utilizzano l'algoritmo di Dijkstra per ottimizzare i percorsi di trasmissione dell'energia nelle reti, al fine di minimizzare le perdite di energia ed evitare sovraccarichi.

Esempio:

Nelle reti elettriche, ogni nodo rappresenta una sottostazione e gli archi sono linee elettriche con diversi livelli di resistenza. L'algoritmo di Dijkstra aiuta a trovare il percorso con la minore resistenza dalla fonte di energia al consumatore.

7. Sistemi di evacuazione e pianificazione del percorso

Ottimizzazione dei percorsi di evacuazione negli edifici o nelle città per un'uscita rapida e sicura in caso di emergenze.

Applicazione:

Architetti e ingegneri utilizzano l'algoritmo di Dijkstra per pianificare i percorsi di evacuazione, per garantire la rimozione sicura e veloce delle persone dalle aree pericolose.

Esempio:

In un condominio o in un edificio per uffici, i nodi del grafo rappresentano le stanze e i corridoi, e gli archi sono i percorsi tra di essi. L'algoritmo di Dijkstra può essere utilizzato per trovare il percorso più breve da qualsiasi punto nell'edificio all'uscita più vicina.

2
Compito
Python SELF IT, livello 56, lezione 3
Bloccato
Città e liste
Città e liste
Commenti
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION