El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Algorisme de Dijkstra

Següent ►
►

Introducció

L'algorisme de Dijkstra és un algorisme clàssic utilitzat per trobar el camí més curt des d'un node origen a tots els altres nodes en un graf amb pesos no negatius. Aquest algorisme és àmpliament utilitzat en xarxes de comunicació, sistemes de navegació i altres aplicacions que requereixen la determinació de rutes òptimes.

Conceptes Clau

Abans d'entrar en l'algorisme, és important entendre alguns conceptes bàsics:

  • Graf: Una col·lecció de nodes (o vèrtexs) i arestes (o arcs) que connecten parelles de nodes.
  • Pes: Un valor associat a una aresta que representa el cost o la distància entre dos nodes.
  • Camí: Una seqüència de nodes connectats per arestes.
  • Camí més curt: El camí amb el menor pes total entre dos nodes.

Funcionament de l'Algorisme

L'algorisme de Dijkstra segueix aquests passos:

  1. Inicialització:

    • Assigna una distància inicial de 0 al node origen i ∞ (infinit) a tots els altres nodes.
    • Marca tots els nodes com no visitats.
    • Estableix el node origen com el node actual.

  2. Iteració:

    • Per al node actual, considera tots els seus veïns no visitats i calcula les seves distàncies temporals des del node origen.
    • Si la distància temporal calculada per a un veí és menor que la distància actualment assignada, actualitza la distància.
    • Després de considerar tots els veïns del node actual, marca el node actual com visitat.
    • Selecciona el node no visitat amb la distància més petita com el nou node actual i repeteix el procés.

  3. Finalització:

    • L'algorisme finalitza quan tots els nodes han estat visitats o quan el node amb la distància més petita és ∞.

Exemple Pràctic

Considerem un graf amb els següents nodes i arestes amb pesos:

    (A)
   / | \
  1  4  2
 /   |   \
(B)  2   (C)
 \   |   /
  5  1  3
   \ | /
    (D)

Pas a Pas

  1. Inicialització:

    • Distàncies: A=0, B=∞, C=∞, D=∞
    • Nodes no visitats: {A, B, C, D}
    • Node actual: A

  2. Iteració 1:

    • Veïns de A: B, C, D
    • Distàncies temporals: B=1, C=2, D=4
    • Actualització: Distàncies: A=0, B=1, C=2, D=4
    • Marcar A com visitat
    • Nou node actual: B (distància més petita)

  3. Iteració 2:

    • Veïns de B: A, D
    • Distàncies temporals: D=6 (no s'actualitza perquè 6 > 4)
    • Marcar B com visitat
    • Nou node actual: C (distància més petita)

  4. Iteració 3:

    • Veïns de C: A, D
    • Distàncies temporals: D=3 (s'actualitza perquè 3 < 4)
    • Actualització: Distàncies: A=0, B=1, C=2, D=3
    • Marcar C com visitat
    • Nou node actual: D

  5. Iteració 4:

    • Veïns de D: A, B, C
    • Tots els veïns ja han estat visitats
    • Marcar D com visitat

  6. Finalització:

    • Tots els nodes han estat visitats
    • Distàncies finals: A=0, B=1, C=2, D=3

Implementació en Python

A continuació es mostra una implementació de l'algorisme de Dijkstra en Python:

import heapq

def dijkstra(graf, origen):
    distàncies = {node: float('infinity') for node in graf}
    distàncies[origen] = 0
    pq = [(0, origen)]
    
    while pq:
        distància_actual, node_actual = heapq.heappop(pq)
        
        if distància_actual > distàncies[node_actual]:
            continue
        
        for veí, pes in graf[node_actual].items():
            distància = distància_actual + pes
            
            if distància < distàncies[veí]:
                distàncies[veí] = distància
                heapq.heappush(pq, (distància, veí))
    
    return distàncies

# Exemple de graf
graf = {
    'A': {'B': 1, 'C': 2, 'D': 4},
    'B': {'A': 1, 'D': 5},
    'C': {'A': 2, 'D': 1},
    'D': {'A': 4, 'B': 5, 'C': 1}
}

origen = 'A'
distàncies = dijkstra(graf, origen)
print(distàncies)

Explicació del Codi

  1. Inicialització:

    • distàncies: Un diccionari que emmagatzema la distància mínima des del node origen a cada node.
    • pq: Una cua de prioritat (min-heap) que emmagatzema els nodes a explorar.

  2. Iteració:

    • heapq.heappop(pq): Extreu el node amb la distància més petita.
    • Si la distància actual és major que la distància emmagatzemada, es continua amb el següent node.
    • Per a cada veí del node actual, es calcula la nova distància.
    • Si la nova distància és menor que la distància emmagatzemada, s'actualitza i s'afegeix a la cua de prioritat.

  3. Finalització:

    • El diccionari distàncies conté les distàncies mínimes des del node origen a cada node.

Exercici Pràctic

Enunciat

Donat el següent graf, implementa l'algorisme de Dijkstra per trobar el camí més curt des del node 'A' a tots els altres nodes:

    (A)
   / | \
  3  1  4
 /   |   \
(B)  2   (C)
 \   |   /
  6  3  5
   \ | /
    (D)

Solució

graf = {
    'A': {'B': 3, 'C': 4, 'D': 1},
    'B': {'A': 3, 'D': 6},
    'C': {'A': 4, 'D': 5},
    'D': {'A': 1, 'B': 6, 'C': 5}
}

origen = 'A'
distàncies = dijkstra(graf, origen)
print(distàncies)

Resultat Esperat

{'A': 0, 'B': 3, 'C': 4, 'D': 1}

Resum

L'algorisme de Dijkstra és una eina poderosa per trobar el camí més curt en grafs amb pesos no negatius. Comprendre aquest algorisme i la seva implementació és fonamental per a qualsevol professional que treballi amb xarxes, rutes o optimització de camins. Practicar amb diferents grafs i pesos ajudarà a consolidar els conceptes i habilitats necessàries per aplicar aquest algorisme en situacions reals.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats