Problema do caminho mais curto em um grafo

Como executar

1. Crie o ambiente virtual digitando o seguinte comando no terminal: python -m venv venv.
2. Ative o ambiente virtual digitando o seguinte comando no terminal: source venv/bin/activate.
3. Instale as dependências digitando o seguinte comando no terminal: pip install -r requirements.txt.
4. Para executar digite python src/main.py.

Fluxo de execução

1. É dado ao usuário a possibilidade de escolher o número de nós que ele quer e também a probabilidade de gerar uma aresta entre um nó e outro.

2. É criado o grafo com a função abaixo:

def create_random_graph(num_nodes, prob_edge, min_weight=1, max_weight=10):
    G = nx.Graph()
    G.add_nodes_from(range(num_nodes))
    for i in range(num_nodes):
        for j in range(i + 1, num_nodes):
            if random.random() < prob_edge:
                weight = random.randint(min_weight, max_weight)
                G.add_edge(i, j, weight=weight)
    return G

3. Após criar o grafo, o programa entra em um loop que dá ao usuário a possibilidade de escolher o nó de começo e o nó de chegada, para posteriormente executar o caminhamento.

4. Escolhendo o nó de chegada e o nó de chegada, deve ser escolhido o algoritmo para executar o caminhamento no grafo, sendo eles:

   • Busca em largura (BFS)
   • Busca em profundidade (DFS)
   • A-estrela com eurística Euclidiana
   • A-estrela com eurística Manhattan

5. Caso as opções de A-estrela sejam escolhidas, as heurísticas são definidas com bases nas funções abaixo:

def heuristic_manhattan(pos, node, goal):
    x1, y1 = pos[node] # Pega as coordenadas x e y do nó inicial
    x2, y2 = pos[goal] # Pega as coordenadas x e y do nó final
    return abs(x1 - x2) + abs(y1 - y2)

def heuristic_euclidean(pos, node, goal):
    x1, y1 = pos[node] # Pega as coordenadas x e y do nó inicial
    x2, y2 = pos[goal] # Pega as coordenadas x e y do nó final
    return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)

6. A função que executa o algoritmo A* é a seguinte abaixo:

def a_star_search(G, start, goal, pos, heuristic):
    open_set = [(0, start)] # Fila de prioridade contendo o custo estimado (f_score) e o nó
    came_from = {} # Dicionário para armazenar o caminho
    g_score = {node: float('inf') for node in G.nodes()} # Custo acumulado para chegar a cada nó
    g_score[start] = 0 # Custo para chegar ao nó inicial é zero
    f_score = {node: float('inf') for node in G.nodes()} # Custo estimado total para chegar ao objetivo
    f_score[start] = heuristic(pos, start, goal) # Estima o custo inicial (heurística) do nó inicial ao objetivo

    while open_set: # Enquanto houver nós para explorar
        _, current = heapq.heappop(open_set) # Retira o nó com o menor f_score da fila de prioridade
        
        if current == goal: # Se o nó atual é o objetivo, retorna o caminho encontrado
            print(f"\nDistância percorrida: {g_score[current]}")
            return reconstruct_path(came_from, current)

        for neighbor in G.neighbors(current): # Para cada vizinho do nó atual
            tentative_g_score = g_score[current] + G[current][neighbor]['weight'] # Calcula o g_score temporário

            if tentative_g_score < g_score[neighbor]: # Se o custo acumulado atual for menor
                came_from[neighbor] = current # Atualiza o caminho
                g_score[neighbor] = tentative_g_score # Atualiza o g_score
                f_score[neighbor] = tentative_g_score + heuristic(pos, neighbor, goal) # Atualiza o f_score (g_score + heurística)
                heapq.heappush(open_set, (f_score[neighbor], neighbor)) # Adiciona o vizinho na fila de prioridade

    return None # Retorna None se não encontrar um caminho

7. A função que executa o algoritmo BFS é a seguinte abaixo:

def bfs_search(G, start, goal):
    queue = deque([start]) # Fila para armazenar os nós a serem explorados (FIFO)
    came_from = {start: None} # Dicionário para armazenar o caminho de volta de cada nó até o início
    distance = {start: 0} # Contador de distância percorrida
    
    while queue:
        current_node = queue.popleft() # Extrair o nó atual da fila
        
        if current_node == goal: # Se o nó atual for o objetivo, reconstruir o caminho e retorná-lo
            path = []
            print(f"Distância percorrida: {distance[goal]}")
            while current_node is not None:
                path.append(current_node)
                current_node = came_from[current_node]
            return path[::-1]  # Retorna o caminho na ordem correta (do início ao objetivo)
        
        for neighbor in G.neighbors(current_node): # Expandir os nós vizinhos do nó atual
            if neighbor not in came_from:  # Se o vizinho ainda não foi visitado
                queue.append(neighbor)  # Adicionar o vizinho à fila
                came_from[neighbor] = current_node  # Registrar o caminho de volta
                edge_weight = G[current_node][neighbor]['weight'] # Peso da aresta atual
                distance[neighbor] = distance[current_node] + edge_weight # Soma ao contador
    
    return None  # Se a fila esvaziar e o objetivo não for encontrado, retorna None

8. A função que executa o algoritmo DFS é a seguinte abaixo:

def dfs_search(G, start, goal):
    stack = [start]  # Inicializa a pilha com o nó inicial
    came_from = {}  # Dicionário para registrar de onde veio cada nó
    visited = set() # Conjunto de nós já visitados
    distance = {start: 0} # Contador de distância percorrida

    while stack:  # Enquanto houver nós na pilha para serem explorados
        current = stack.pop() # Remove o nó do topo da pilha para ser o nó atual
        if current == goal:  # Verifica se o nó atual é o objetivo
            print(f"Distância percorrida: {distance[goal]}")
            return reconstruct_path(came_from, current) # Reconstrói o caminho até o objetivo
        
        if current not in visited: # Se o nó ainda não foi visitado
            visited.add(current) # Marca o nó como visitado
            for neighbor in G.neighbors(current): # Explora todos os vizinhos do nó atual
                if neighbor not in visited: # Se o vizinho ainda não foi visitado
                    came_from[neighbor] = current # Marca que chegamos no vizinho a partir do nó atual
                    stack.append(neighbor) # Adiciona o vizinho na pilha para ser explorado
                    edge_weight = G[current_node][neighbor]['weight'] # Peso da aresta atual
                    distance[neighbor] = distance[current_node] + edge_weight # Soma ao contador
                    
    return None # Se não encontrou o objetivo, retorna None

9. Encontrando nó de destino, é feita a reconstrução do grafo para poder ser visualizado o caminho percorrido. Isso é feito com o código abaixo:

def reconstruct_path(came_from, current):
    total_path = [current]
    while current in came_from:
        current = came_from[current]
        total_path.insert(0, current)
    return total_path

10. Após reconstruir o grafo, o grafo finalmente pode ser visualizado com a função abaixo:

def visualize_graph(G, path=None):
    edges = G.edges(data=True)

    edge_colors = ['black'] * len(G.edges())

    if path:
        edge_list = list(zip(path, path[1:]))
        edge_colors = ['red' if (u, v) in edge_list or (v, u) in edge_list else 'black' for u, v in G.edges()]

    nx.draw(G, nx.spring_layout(G, seed=42), with_labels=True, node_size=200, font_size=10)
    nx.draw_networkx_edge_labels(G, nx.spring_layout(G, seed=42), edge_labels={(u, v): f'{d["weight"]}' for u, v, d in edges})
    nx.draw(G, nx.spring_layout(G, seed=42), edgelist=G.edges(), edge_color=edge_colors, width=1)
    
    plt.show()