TREINAMENTO PARA COMPETIÇÕES DE PROGRAMAÇÃO

GRAFOS - PARTE IIISINGLE-SOURCE SHORTEST PATHS:

DIJKSTRA E BELLMAN-FORD

Murilo Adriano Vasconceloshttp://murilo.wordpress.com

O problema

• Dado um grafo ponderado G(V, E), onde as arestas tem custos positivos, queremos saber qual o custo do menor caminho de um vértice origem u ∈ V para todos os outros vértices v ∈ V.

O algoritmo de Dijkstraconst int MAXV = 1000; // número máximo de vérticesconst int INF = 0x3f3f3f3f; // cuidado com esse valorlist< pair<int, int> > grafo[MAXV]; // lista de adjacênciaint dist[MAXV]; // a resposta ficará neste vetorint visited[MAXV], N; // N é a quantidade de vértices atual

void leitura() {

cin >> N >> m; // quantidade de vertices e arestasint de, para, custo;// limpa o grafofor (int i = 0; i < N; ++i) g[i].clear();

// leitura da entradafor (int i = 0; i < m; ++i) {

cin >> de >> para >> custo;g[de].push_back(make_pair(para, custo));

}}

O algoritmo de Dijkstra

void dijkstra(int origem){

for (int i = 0; i < N; ++i) {dist[i] = INF;visited[i] = false;

}

// nossa heap de máximo onde: first = custo, // second = verticepriority_queue< pair<int, int> > pq;pq.push(make_pair(0, origem));dist[origem] = 0; // distancia da origem pra ela

// mesma é 0

pair<int, int> atual;list< pair<int, int> >::iterator it;

O algoritmo de Dijkstrawhile (!pq.empty()) {

atual = pq.top();pq.pop();

int custo = -atual.first; // nao esqueça do ‘-’!int v = atual.second;

if (visited[v]) continue; // já processamos elevisited[v] = true; // se cheguei aqui, o menor custo

// de origem para v já foi calculado

// para cada aresta, tentamos fazer a relaxaçãofor (it = g[v].begin(); it != g[v].end(); ++it) {

if (dist[it->second] > w + it->first) { dist[it->second] = w + it->first; pq.push(make_pair(-dist[it->second], it->second)); }

}}

} // dijkstra

O algoritmo de Dijkstra

• Inicialmente, colocamos na heap, o vértice de origem com o custo 0 e dizemos que o custo da origem para origem é 0

• Em seguida, para cada elemento v com o menor custo (top() na priority_queue), tentamos relaxar (diminuindo) o custo dos seus vizinhos

• Se o custo de algum vértice u for maior que o custo de v mais o custo da aresta que liga o v a u, diminuímos o custo de u para este valor

Dijkstra - demonstração

Dijkstra - análise

• Complexidade O(|E| log |V|)

• |V| = 1000, |E| = 100.000 < 10^6 operações (feasible)

• Comparativo com Floyd-Warshall O(|V|^3)

• |V| = 1000, 10^9 operações (geralmente unfeasible)

Outro problema

• Dado um grafo ponderado G(V, E), onde as arestas podem ter custos negativos, queremos saber qual o custo do menor caminho de um vértice origem u ∈ V para todos os outros vértices v ∈ V.

Usar o Dijkstra?

• Seja G, este grafo:

0 1 3

2

4102

-1 -4

1

Usar o Dijkstra?

Seja G, este grafo:

0 1 3

2

4102

-1 -4

1

Qual a menor distância entre 0 e 4?

Usar o Dijkstra?

Não podemos usar o Dijkstra, pois o grafo contém um ciclo negativo.

0 1 3

2

4102

-1 -4

1

Podemos ficar infinitamente neste ciclo pois o custo sempre diminuirá

O algoritmo Bellman-Ford

• O algoritmo de Bellman-Ford encontra o menor caminho entre um vértice origem e todos os outros se o grafo não tiver ciclos negativos

• Se o grafo tiver ciclos negativos, o algoritmo serve para detectá-los

O algoritmo Bellman-Ford

• Utiliza a representação de lista de arestas

• Faz a relaxação utilizando a desigualdade triangular |V| - 1 vezes

• Se após |V| - 1 relaxações, ainda conseguirmos diminuir o custo de algum vértice, o grafo contém ciclos negativos

O algoritmo Bellman-Fordconst int MAXV = 1000; // número máximo de vérticesconst int INF = 0x3f3f3f3f; // cuidado com esse valor

struct aresta { int u, v, w; }; // de, para, custovector<aresta> grafo; // pode ser um array se

// soubermos o máximo de arestasint custo[MAXV], N, E; // custo, vértices, arestas

void le(){

cin >> N >> E; // le a quant. de vértices e arestas

grafo.clear();aresta ar;for (int i = 0; i < E; ++i) {

cin >> ar.u >> ar.v >> ar.w; // de, para, custografo.push_back(ar);

}}

O algoritmo Bellman-Ford

bool bellan_ford(int origem){

for (int i = 0; i < V; ++i) custo[i] = INF;custo[origem] = 0;for (int i = 0; i < V - 1; ++i) { // até V - 1

for (int j = 0; j < E; ++j) {int u = grafo[j].u;int v = grafo[j].v;int w = grafo[j].w;

// relaxaçãoif (custo[v] > custo[u] + w) {

custo[v] = custo[u] + w;}

}}

O algoritmo Bellman-Ford

// checagem de ciclos de custo negativofor (int j = 0; j < E; ++j) {

int u = grafo[j].u;int v = grafo[j].v;int w = grafo[j].w;

// se ainda é possível diminuir o custo// é porque sempre vai ter como (ciclo negativo)if (custo[v] > custo[u] + w) {

return false; // ciclo encontrado}

}

return true; // nenhum ciclo negativo

} // bellman_ford()

Bellman-Ford - análise

• Complexidade O(VE)

• Loop de fora V vezes, loop interno E vezes

Alguns Problemas

Dijkstra (UVA):341 - Non-Stop Travel929 - Number Maze

  1202 - Finding Nemo 10166 - Travel 10269 - Adventure of Super Mario 10278 - Fire Station 10389 - Subway 10603 - Fill 10801 - Lift Hopping 10986 - Sending email 11367 - Full Tank? 11377 - Airport Setup 11492 - Babel 11833 - Route Change 12138 - Chemical Plant

Bellman Ford (UVA): 558 - Wormholes 10557 - XYZZY 11280 - Flying to Fredericton

Dúvidas?