Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como achar a maior distância entre dois vértices em um grafo/rede (longest simple path problem)?

0 votos
11 visitas
perguntada Nov 4 em Sistemas Complexos por Renan Abrantes (16 pontos)  
editado Nov 4 por Renan Abrantes

A questão é proveniente do problema 2.26 do livro "Dynamic Programming: A Computational Tool", por Art Lew e Holger Mauch.

O longest simple path problem é um problema conhecido na teoria de redes, incrustado na classe mais ampla de problemas que têm o objetivo de medir distâncias entre dois vértices. Já o termo simple path significa que essa distância deve ser medida sem que se possa repetir algum vértice no meio do caminho.

Neste caso, vamos achar a maior distância entre dois vértices em uma rede ponderada (weighted), sem repetir vértice algum no caminho.

Compartilhe

1 Resposta

0 votos
respondida Nov 4 por Renan Abrantes (16 pontos)  
editado Nov 6 por Renan Abrantes

Inicialmente, eu entendi que este problema seria para gráficos não direcionados, o que permitiria o uso do algoritmo de Dijkstra com adaptações. Ao reler o problema, percebi que deveria ser feito para uma rede direcionada.

Infelizmente, só consegui implementar a solução para uma rede ponderada direcionada sem ciclos, conhecida como directed acyclic graph (DAG).

Utilizei um DFS seguido de um topological sort. Para achar a maior distância, posteriormente utilizei o algortimo de Bellman-Ford.

Segue a implementação para uma rede representa por uma lista de adjacência:

import sys

class Grafo:
    # Construtor
    def __init__(self, edges, n):

        # Lista de listas para representar uma adjacency list
        self.adjList = [[] for i in range(n)]

        # Adiciona edges para o grafo direcionado
        for (origem, dest, weight) in edges:
            self.adjList[origem].append((dest, weight))


    # Algoritmo de DFS no grafo
def DFS(grafo, v, usado, partida, passos):

    # marcar o vértice atual como usado
    usado[v] = True

    # para cada edge
    for (u, w) in grafo.adjList[v]:
        # if `u` is not yet usado
        if not usado[u]:
            passos = DFS(grafo, u, usado, partida, passos)

    partida[passos] = v
    passos = passos + 1

    return passos

# Realiza topological sort e acha a maior distância de todos os vértices a partir de um vértice i,
# utilizando o algoritmo de Bellman–Ford
def acharMaiorDist(grafo, origem, n):

    partida = [-1] * n
    #para saber se um vértice está sendo usado
    usado = [False] * n
    passos = 0

    # perform DFS on all unusado vertices
    for i in range(n):
        if not usado[i]:
            passos = DFS(grafo, i, usado, partida, passos)

    custo = [sys.maxsize] * n
    custo[origem] = 0

    #Processar os vértices em ordem topológica
    for i in reversed(range(n)):

        # para cada vértice na ordem, relaxar o custo de seus vizinhos
        v = partida[i]

        for (u, w) in grafo.adjList[v]:
            w = -w  # fazer o peso ser negativo (importante para achar maior me vez de menor distância)

            # se a distância ao destino pode ser aumentada colocando um vértice no caminho, atualizar
            if custo[v] != sys.maxsize and custo[v] + w < custo[u]:
                custo[u] = custo[v] + w

    # mostra as maiores distância do vértice de origem para outros vértices
    for i in range(n):
        print(f'dist ({origem}, {i}) = {-custo[i]}')

Agora vamos testar o programa para uma lista de adjacência abaixo determinada:

if __name__ == '__main__':

    # grafo em forma de adjacency list, com peso no final de cada conexão
    edges = [(0, 6, 2), (1, 3, 10), (1, 5, 1),(1, 6, 8), (3, 0, 4), (3, 4, 9),
    (5, 1, 2), (7, 0, 6), (7, 1, 25), (7, 3, 4), (7, 5, 15)]
    # número total de vértices no grafo
    n = 8
    # construir a rede
    grafo = Grafo(edges, n)
    # vértice de origem para o cálculo das maiores distâncias
    origem = 7
    # encontra as maiores distâncias dado o vértice de origem
    acharMaiorDist(grafo, origem, n)

Segue o resultado da implementação:

A imagem será apresentada aqui.

comentou Nov 6 por Fábio Springer (11 pontos)  
Legal a sua resposta. Dei uma pesquisada e descobri que existe um algoritmo mais eficiente do que Bellman-Ford, o Shortest Path Faster Algorithm que nada mais é do que uma modificação do Bellman-Ford e reduz a quantidade de interações.  A ideia é adicionar uma fila de vértices e um vértice é adicionado à fila apenas se esse vértice estiver atualizando o custo de todos os vértices conectados se os custos forem melhorados incluindo o caminho através do vértice v.

Encontrei esse post que explica bem o SPF e ainda apresenta implementações em python, C, C# e Java.  https://www.geeksforgeeks.org/shortest-path-faster-algorithm/
comentou Nov 8 por Renan Abrantes (16 pontos)  
Fábio, obrigado pela observação. Não conhecia o SPF. Imagino que seja possível adaptá-lo para achar as maiores distâncias entre os vértices em um grafo direcionado ponderado cíclico, mas não encontrei menção a isso em pesquisa na internet. Eu sei que existem alguns algoritmos que só servem para um problema específico, com o caso do Dijkstra para grafos não direcionados.
...