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

Algoritmes de Camins Mínims

Següent ►
►

En aquest tema, explorarem els algoritmes que ens permeten trobar el camí més curt entre dos nodes en un graf. Aquests algoritmes són fonamentals en moltes aplicacions, com ara la navegació GPS, les xarxes de comunicació i la logística. Ens centrarem en els següents algorismes:

  1. Algoritme de Dijkstra
  2. Algoritme de Bellman-Ford
  3. Algoritme de Floyd-Warshall
  4. Algoritme de Johnson

  1. Algoritme de Dijkstra

Descripció

L'algoritme de Dijkstra és un algorisme de recorregut en grafs que troba el camí més curt des d'un node origen a tots els altres nodes en un graf amb pesos no negatius.

Pseudocodi

Dijkstra(G, s)
  per a cada node v en G
    dist[v] := infinit
    anterior[v] := no definit
  dist[s] := 0
  Q := tots els nodes de G

  mentre Q no estigui buit
    u := node en Q amb dist[u] mínim
    eliminar u de Q

    per a cada veí v de u
      alt := dist[u] + pes(u, v)
      si alt < dist[v]
        dist[v] := alt
        anterior[v] := u

  retornar dist[], anterior[]

Exemple

Considerem el següent graf:

    A
   / \
  1   4
 /     \
B-------C
 \     /
  2   1
   \ /
    D

Aplicarem l'algoritme de Dijkstra des del node A.

Implementació en Python

import heapq

def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]
    prev = {node: None for node in graph}

    while pq:
        current_dist, current_node = heapq.heappop(pq)

        if current_dist > dist[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_dist + weight

            if distance < dist[neighbor]:
                dist[neighbor] = distance
                prev[neighbor] = current_node
                heapq.heappush(pq, (distance, neighbor))

    return dist, prev

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 2},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 2, 'C': 1}
}

distances, previous_nodes = dijkstra(graph, 'A')
print("Distàncies:", distances)
print("Nodes anteriors:", previous_nodes)

Exercici Pràctic

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

    S
   /|\
  7 | 9
 /  |  \
A---B---C
 \  |  /
  2 | 4
   \|/
    D

  1. Algoritme de Bellman-Ford

Descripció

L'algoritme de Bellman-Ford és capaç de trobar el camí més curt des d'un node origen a tots els altres nodes en un graf, fins i tot si aquest conté arestes amb pesos negatius. A més, pot detectar cicles de pes negatiu.

Pseudocodi

BellmanFord(G, s)
  per a cada node v en G
    dist[v] := infinit
    anterior[v] := no definit
  dist[s] := 0

  per i de 1 a |V| - 1
    per a cada aresta (u, v) en G
      si dist[u] + pes(u, v) < dist[v]
        dist[v] := dist[u] + pes(u, v)
        anterior[v] := u

  per a cada aresta (u, v) en G
    si dist[u] + pes(u, v) < dist[v]
      error "Graf conté un cicle de pes negatiu"

  retornar dist[], anterior[]

Exemple

Considerem el següent graf amb pesos negatius:

    A
   / \
  1  -3
 /     \
B-------C
 \     /
  2   1
   \ /
    D

Aplicarem l'algoritme de Bellman-Ford des del node A.

Implementació en Python

def bellman_ford(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    prev = {node: None for node in graph}

    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor, weight in graph[node].items():
                if dist[node] + weight < dist[neighbor]:
                    dist[neighbor] = dist[node] + weight
                    prev[neighbor] = node

    for node in graph:
        for neighbor, weight in graph[node].items():
            if dist[node] + weight < dist[neighbor]:
                raise ValueError("Graf conté un cicle de pes negatiu")

    return dist, prev

graph = {
    'A': {'B': 1, 'C': -3},
    'B': {'A': 1, 'C': 2, 'D': 2},
    'C': {'A': -3, 'B': 2, 'D': 1},
    'D': {'B': 2, 'C': 1}
}

distances, previous_nodes = bellman_ford(graph, 'A')
print("Distàncies:", distances)
print("Nodes anteriors:", previous_nodes)

Exercici Pràctic

Donat el següent graf amb pesos negatius, aplica l'algoritme de Bellman-Ford per trobar el camí més curt des del node 'S' a tots els altres nodes:

    S
   /|\
  7 | -9
 /  |  \
A---B---C
 \  |  /
  2 | 4
   \|/
    D

  1. Algoritme de Floyd-Warshall

Descripció

L'algoritme de Floyd-Warshall és un algorisme per trobar els camins més curts entre tots els parells de nodes en un graf. És especialment útil per a grafs densos.

Pseudocodi

FloydWarshall(G)
  dist := array de |V| x |V| inicialitzat a infinit
  per a cada node v en G
    dist[v][v] := 0
  per a cada aresta (u, v) en G
    dist[u][v] := pes(u, v)

  per k de 1 a |V|
    per i de 1 a |V|
      per j de 1 a |V|
        si dist[i][j] > dist[i][k] + dist[k][j]
          dist[i][j] := dist[i][k] + dist[k][j]

  retornar dist

Exemple

Considerem el següent graf:

    A
   / \
  1   4
 /     \
B-------C
 \     /
  2   1
   \ /
    D

Aplicarem l'algoritme de Floyd-Warshall.

Implementació en Python

def floyd_warshall(graph):
    nodes = list(graph.keys())
    dist = {node: {node2: float('inf') for node2 in nodes} for node in nodes}
    
    for node in nodes:
        dist[node][node] = 0
    
    for node in graph:
        for neighbor, weight in graph[node].items():
            dist[node][neighbor] = weight
    
    for k in nodes:
        for i in nodes:
            for j in nodes:
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 2},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 2, 'C': 1}
}

distances = floyd_warshall(graph)
print("Distàncies:", distances)

Exercici Pràctic

Donat el següent graf, aplica l'algoritme de Floyd-Warshall per trobar els camins més curts entre tots els parells de nodes:

    S
   /|\
  7 | 9
 /  |  \
A---B---C
 \  |  /
  2 | 4
   \|/
    D

  1. Algoritme de Johnson

Descripció

L'algoritme de Johnson és una combinació dels algorismes de Bellman-Ford i Dijkstra que permet trobar els camins més curts entre tots els parells de nodes en un graf amb pesos negatius, però sense cicles de pes negatiu.

Pseudocodi

Johnson(G)
  afegir un node q a G amb arestes de pes 0 a tots els altres nodes
  h := BellmanFord(G, q)
  per a cada aresta (u, v) en G
    pes(u, v) := pes(u, v) + h[u] - h[v]
  eliminar q de G
  per a cada node u en G
    dist[u] := Dijkstra(G, u)
    per a cada node v en G
      dist[u][v] := dist[u][v] + h[v] - h[u]
  retornar dist

Exemple

Considerem el següent graf amb pesos negatius:

    A
   / \
  1  -3
 /     \
B-------C
 \     /
  2   1
   \ /
    D

Aplicarem l'algoritme de Johnson.

Implementació en Python

def bellman_ford(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    prev = {node: None for node in graph}

    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor, weight in graph[node].items():
                if dist[node] + weight < dist[neighbor]:
                    dist[neighbor] = dist[node] + weight
                    prev[neighbor] = node

    for node in graph:
        for neighbor, weight in graph[node].items():
            if dist[node] + weight < dist[neighbor]:
                raise ValueError("Graf conté un cicle de pes negatiu")

    return dist, prev

def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]
    prev = {node: None for node in graph}

    while pq:
        current_dist, current_node = heapq.heappop(pq)

        if current_dist > dist[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_dist + weight

            if distance < dist[neighbor]:
                dist[neighbor] = distance
                prev[neighbor] = current_node
                heapq.heappush(pq, (distance, neighbor))

    return dist, prev

def johnson(graph):
    new_graph = {node: neighbors.copy() for node, neighbors in graph.items()}
    new_graph['q'] = {node: 0 for node in graph}

    h, _ = bellman_ford(new_graph, 'q')

    for u in graph:
        for v in graph[u]:
            graph[u][v] += h[u] - h[v]

    del new_graph['q']

    dist = {}
    for u in graph:
        dist[u], _ = dijkstra(graph, u)
        for v in dist[u]:
            dist[u][v] += h[v] - h[u]

    return dist

graph = {
    'A': {'B': 1, 'C': -3},
    'B': {'A': 1, 'C': 2, 'D': 2},
    'C': {'A': -3, 'B': 2, 'D': 1},
    'D': {'B': 2, 'C': 1}
}

distances = johnson(graph)
print("Distàncies:", distances)

Exercici Pràctic

Donat el següent graf amb pesos negatius, aplica l'algoritme de Johnson per trobar els camins més curts entre tots els parells de nodes:

    S
   /|\
  7 | -9
 /  |  \
A---B---C
 \  |  /
  2 | 4
   \|/
    D

Conclusió

En aquesta secció, hem explorat diversos algorismes per trobar els camins més curts en grafs. Hem après a utilitzar l'algoritme de Dijkstra per a grafs amb pesos no negatius, l'algoritme de Bellman-Ford per a grafs amb pesos negatius, l'algoritme de Floyd-Warshall per a trobar els camins més curts entre tots els parells de nodes, i l'algoritme de Johnson per a grafs amb pesos negatius però sense cicles de pes negatiu. Aquests algorismes són fonamentals en moltes aplicacions pràctiques i ens proporcionen eines poderoses per resoldre problemes complexos en grafs.

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