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

Algoritmes de Camins Mínims

Següent ►
►

Els algoritmes de camins mínims són fonamentals en l'estudi dels grafs, ja que permeten trobar el camí més curt entre dos nodes en un graf. Aquests algoritmes tenen aplicacions en diverses àrees, com ara la navegació GPS, les xarxes de comunicació, i la planificació de rutes.

Conceptes Clau

Abans de començar amb els algoritmes, és important entendre alguns conceptes bàsics:

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

Algoritmes Principals

Algoritme de Dijkstra

L'algoritme de Dijkstra és un dels més coneguts per trobar el camí mínim en un graf amb pesos no negatius.

Pas a Pas

  1. Inicialització:

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

  2. Actualització de distàncies:

    • Per al node actual, considera tots els seus veïns no visitats.
    • Calcula la distància total des del node d'origen fins a cada veí passant pel node actual.
    • Si aquesta distància és menor que la distància actualment assignada al veí, actualitza la distància.

  3. Marcar com visitat:

    • Marca el node actual com visitat.
    • Un node visitat no serà revisitat.

  4. Seleccionar el següent node:

    • Tria el node no visitat amb la menor distància assignada com el següent node "actual".
    • Repeteix els passos 2-4 fins que tots els nodes hagin estat visitats o la menor distància entre els nodes no visitats sigui ∞.

Exemple en Python

import heapq

def dijkstra(graph, start):
    # Inicialització
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    
    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)
        
        # Nodes ja visitats
        if current_distance > distances[current_node]:
            continue
        
        # Actualització de distàncies
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances

# Exemple de graf
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}
}

print(dijkstra(graph, 'A'))

Algoritme de Bellman-Ford

L'algoritme de Bellman-Ford és capaç de trobar el camí mínim en grafs amb pesos negatius.

Pas a Pas

  1. Inicialització:

    • Assigna una distància inicial de 0 al node d'origen i ∞ a tots els altres nodes.

  2. Relaxació de les arestes:

    • Per a cada aresta, si la distància al node de destinació pot ser reduïda passant pel node d'origen, actualitza la distància.

  3. Repetició:

    • Repeteix el pas 2 per a totes les arestes (V-1) vegades, on V és el nombre de nodes.

  4. Comprovació de cicles negatius:

    • Torna a revisar totes les arestes. Si es pot reduir alguna distància, hi ha un cicle negatiu en el graf.

Exemple en Python

def bellman_ford(graph, start):
    # Inicialització
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    
    # Relaxació de les arestes
    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor, weight in graph[node].items():
                if distances[node] + weight < distances[neighbor]:
                    distances[neighbor] = distances[node] + weight
    
    # Comprovació de cicles negatius
    for node in graph:
        for neighbor, weight in graph[node].items():
            if distances[node] + weight < distances[neighbor]:
                raise ValueError("El graf conté un cicle negatiu")
    
    return distances

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

print(bellman_ford(graph, 'A'))

Comparació d'Algoritmes

Algoritme Pesos Negatius Complexitat Temporal Complexitat Espacial Notes
Dijkstra No O(V^2) o O(E + V log V) amb heap O(V) Més eficient per grafs densos amb pesos no negatius
Bellman-Ford Sí O(VE) O(V) Pot detectar cicles negatius

Exercicis Pràctics

  1. Implementació de Dijkstra:

    • Implementa l'algoritme de Dijkstra per a un graf dirigit amb pesos no negatius.
    • Prova'l amb diferents grafs i compara els resultats amb altres implementacions.

  2. Implementació de Bellman-Ford:

    • Implementa l'algoritme de Bellman-Ford per a un graf dirigit amb pesos negatius.
    • Prova'l amb diferents grafs, incloent-hi grafs amb cicles negatius.

  3. Comparació d'Algoritmes:

    • Crea un graf amb pesos variats i compara els resultats i el rendiment dels dos algoritmes.
    • Analitza en quines situacions un algoritme és més eficient que l'altre.

Errors Comuns i Consells

  • No inicialitzar correctament les distàncies: Assegura't que totes les distàncies inicials són ∞ excepte la del node d'origen.
  • No comprovar cicles negatius en Bellman-Ford: És crucial revisar si hi ha cicles negatius després de la relaxació de les arestes.
  • No utilitzar una estructura de dades adequada: En Dijkstra, utilitzar un heap (cua de prioritat) pot millorar significativament l'eficiència.

Conclusió

Els algoritmes de camins mínims són essencials per a la resolució de problemes en grafs. Dijkstra és ideal per a grafs amb pesos no negatius, mentre que Bellman-Ford és útil per a grafs amb pesos negatius i pot detectar cicles negatius. La comprensió i implementació d'aquests algoritmes és fonamental per a qualsevol programador que treballi amb grafs.

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