Introducció

L'algorisme de Floyd-Warshall és un algorisme clàssic per trobar les distàncies mínimes entre tots els parells de nodes en un graf ponderat. És especialment útil en grafs densos i pot manejar pesos negatius, sempre que no hi hagi cicles de pes negatiu.

Conceptes Clau

Graf Ponderat: Un graf on cada aresta té un pes associat.
Matriu de Distàncies: Una matriu que representa les distàncies mínimes entre tots els parells de nodes.
Pes Negatiu: Un pes d'aresta que és negatiu. L'algorisme de Floyd-Warshall pot manejar pesos negatius, però no cicles de pes negatiu.

Pseudocodi

Abans de veure el codi, és útil entendre el pseudocodi de l'algorisme:

funció FloydWarshall(graf):
    n = nombre de nodes en el graf
    dist = matriu de distàncies inicialitzada amb infinit (∞)
    
    per a cada node i en el graf:
        dist[i][i] = 0
    
    per a cada aresta (i, j) amb pes w en el graf:
        dist[i][j] = w
    
    per a cada node k en el graf:
        per a cada node i en el graf:
            per a cada node j en el graf:
                si dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    retorna dist

Implementació en Python

A continuació es mostra una implementació de l'algorisme de Floyd-Warshall en Python:

def floyd_warshall(graph):
    # Nombre de nodes en el graf
    n = len(graph)
    
    # Inicialitzar la matriu de distàncies amb infinit
    dist = [[float('inf')] * n for _ in range(n)]
    
    # Inicialitzar les distàncies de la diagonal principal a 0
    for i in range(n):
        dist[i][i] = 0
    
    # Inicialitzar les distàncies segons les arestes del graf
    for i in range(n):
        for j in range(n):
            if graph[i][j] != 0:
                dist[i][j] = graph[i][j]
    
    # Aplicar l'algorisme de Floyd-Warshall
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

# Exemple d'ús
graph = [
    [0, 3, float('inf'), 5],
    [2, 0, float('inf'), 4],
    [float('inf'), 1, 0, float('inf')],
    [float('inf'), float('inf'), 2, 0]
]

distances = floyd_warshall(graph)
for row in distances:
    print(row)

Explicació del Codi

Inicialització de la Matriu de Distàncies:
- Es crea una matriu dist de n x n on n és el nombre de nodes en el graf.
- Es inicialitzen totes les distàncies a infinit (float('inf')), excepte les diagonals que es posen a 0 perquè la distància d'un node a si mateix és 0.
Assignació de les Distàncies Inicials:
- Es recorre la matriu del graf original i s'assignen les distàncies inicials segons les arestes del graf.
Aplicació de l'Algorisme de Floyd-Warshall:
- Es recorre cada node intermedi k i es verifica si passar per k redueix la distància entre qualsevol parell de nodes i i j.
- Si dist[i][j] > dist[i][k] + dist[k][j], es fa l'actualització dist[i][j] = dist[i][k] + dist[k][j].

Exercici Pràctic

Enunciat

Dona't el següent graf representat com una matriu d'adjacència, implementa l'algorisme de Floyd-Warshall per trobar les distàncies mínimes entre tots els parells de nodes:

graph = [
    [0, 8, float('inf'), 1],
    [float('inf'), 0, 1, float('inf')],
    [4, float('inf'), 0, float('inf')],
    [float('inf'), 2, 9, 0]
]

Solució

def floyd_warshall(graph):
    n = len(graph)
    dist = [[float('inf')] * n for _ in range(n)]
    
    for i in range(n):
        dist[i][i] = 0
    
    for i in range(n):
        for j in range(n):
            if graph[i][j] != 0:
                dist[i][j] = graph[i][j]
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

graph = [
    [0, 8, float('inf'), 1],
    [float('inf'), 0, 1, float('inf')],
    [4, float('inf'), 0, float('inf')],
    [float('inf'), 2, 9, 0]
]

distances = floyd_warshall(graph)
for row in distances:
    print(row)

Resultat Esperat

[0, 3, 2, 1]
[5, 0, 1, 6]
[4, 7, 0, 5]
[7, 2, 3, 0]

Conclusió

L'algorisme de Floyd-Warshall és una eina potent per calcular les distàncies mínimes entre tots els parells de nodes en un graf ponderat. És especialment útil en grafs densos i pot manejar pesos negatius, sempre que no hi hagi cicles de pes negatiu. Amb la implementació i l'exercici pràctic, hem vist com aplicar aquest algorisme de manera efectiva.

Algorisme de Floyd-Warshall

Introducció

Conceptes Clau

Pseudocodi

Implementació en Python

Explicació del Codi

Exercici Pràctic

Enunciat

Solució

Resultat Esperat

Conclusió

Curs d'Anàlisi i Disseny d'Algorismes

Mòdul 1: Introducció als Algorismes

Mòdul 2: Anàlisi d'Algorismes

Mòdul 3: Estratègies de Disseny d'Algorismes

Mòdul 4: Algorismes Clàssics

Mòdul 5: Optimització d'Algorismes

Mòdul 6: Pràctiques i Exercicis