Dijkstra Para Custo Máximo

Estou resolvendo alguns exercícios de grafos não-orientado e implementei o algoritmo de Dijkstra usando lista de adjacência, sei que o algoritmo tem como objetivo achar o caminho de custo mínimo entre um vértice origem e qualquer outro vértice.

Preciso, portanto modificar esse algoritmo de forma com que ele me retorne o custo máximo entre um vértice origem a qualquer outro, gostaria de saber que mudanças posso fazer ao meu código pra alcançar esse objetivo, pois já tentei algumas modificações, como:

  • Fazer com que a priority_queue armazene a maior distancia ao invés da menor.
  • Desenvolver a aresta de maior custo ao invés da de menor.
  • Iniciar demais vértices com exceção do origem com um valor mínimo ao invés do valor máximo.

As modificações relatadas acima funciona para alguns casos de testes apenas, de que forma posso alterar meu algoritmo pra que ele cumpra o meu objetivo ?

#include <iostream>
#include <list>
#include <climits> //int_max
#include <vector>
#include <queue>
#include <iomanip> //setw()

#define INFINITO INT_MAX

using namespace std;

enum Cor {BRANCO, CINZA, PRETO};

struct Vertice{
Cor cor;      
int pred;     // predecessor 
int dist;     //distancia
int custo;    //peso da aresta 
};

class Grafo{
private:
    int numeroDeVertices;
    vector <struct Vertice> vertices; 
    list<pair <int, int> > *adj; //lista de pares adjacentes (vertice destino, custo)
public:
    Grafo(int n);
    void adicionarAresta(int v, int u, int custo);
    void Dijkstra(int origem);
    void listVertices(int numVertices);
};

Grafo::Grafo(int n){
this->numeroDeVertices = n;
this->adj = new list<pair<int, int> >[n];
}

void Grafo::adicionarAresta(int v, int u, int custo){
this->adj[v].push_back(make_pair(u, custo));   
this->adjD[u].push_back(make_pair(v, custo)); //grafo não orientado
}

void Grafo::listVertices(int numVertices){
for(int i = 0; i < numVertices; i++)    {
    cout << "Rotulo | Cor | Distancia | Predecessor\n";
    cout << setw(6) << i
         << setw(5) << vertices[i].cor 
         << setw(12) << vertices[i].dist 
         << setw(10) << vertices[i].pred 
         << endl;
}
}

void Grafo::Dijkstra(int origem){
//fila de prioridades <peso, vertice> levando em conta o menor custo como topo da fila
priority_queue <pair <int, int>, 
                            vector<pair <int, int> >, greater<pair <int, int> > > Q;

//inicia vetor de vertices
for(int u = 0; u < numeroDeVertices; u++){        
    struct Vertice v;
    v.cor = BRANCO;
    v.pred = -1;
    
    if(u != origem)
       v.dist = INFINITO;      
    else
       v.dist = 0;     
  vertices.push_back(v);
}

Q.push(make_pair(0, origem));

while(!Q.empty()){
    int u = Q.top().second; //extrai o vertice do topo
    Q.pop();
    
    if(vertices[u].cor != PRETO){ //se não foi visitado:
        vertices[u].cor = PRETO;

        list<pair <int, int>>::iterator it; //percorrer a lista dos adjacentes à u
        for(it = adj[u].begin(); it != adj[u].end(); it++){
            int v = it->first;
            int custo = it->second;

            //relaxamento
            if(vertices[v].dist > (vertices[u].dist + custo)){ //se grafo nao orientado é preciso verificar se vertices[v] é diferente de PRETO, senão contará a volta
                vertices[v].dist = vertices[u].dist  + custo;
                vertices[v].pred = u; 
                Q.push(make_pair(vertices[v].dist, v)); //insere na fila com o menor distancia no topo
            }
        }
    }
}
}

int main(){
Grafo grafo = Grafo (5);

grafo.adicionarAresta(0,1,3);
grafo.adicionarAresta(1,2,5);
grafo.adicionarAresta(2,4,2);
grafo.adicionarAresta(4,0,8);
grafo.adicionarAresta(1,3,1);
grafo.adicionarAresta(3,4,4);

grafo.Dijkstra(0);

grafo.listVertices(5);
}

Problemas envolvendo a distância mais longa entre destino e origem em um grafo não podem ser resolvidas via Dijkstra, simplesmente porque não existe uma subestrutura ótima ideal que resolva o problema.

O que você pode fazer é inverter o sinal dos pesos, mas neste caso, você corre o risco de obter resultados errados pois o algoritmo não é capaz de garantir que o custo de um caminho vai ser sempre mínimo já que caminhos descartados podem envolver vértices que anulem o custo extra. Simplificando, Dijkstra não funciona com pesos negativos.

Outra possível ideia seria posteriormente somarmos um valor absoluto igual ao custo mais negativo do grafo para nos livrarmos dos custos negativos, porém a estratégia só é garantida caso todos os caminhos possíveis entre a origem e o destino, tenham o mesmo número de vértices intermediários.

2 Curtidas

Não sei se Dijkstra é obrigatório, caso não seja, você pode mudar o sinal dos pesos e utilizar o algoritmo Bellman-Ford.

É mais garantido de funcionar já que você pode detectar loops negativos, e nestes casos particulares, recorrer a resolução tradicional do problema do caminho mais longo.

1 Curtida