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);
}