Algoritmo de Dijkstra

Algoritmo de Dijkstra
classe	Algoritmo de busca
estrutura de dados	Grafo
complexidade pior caso	$O(|E| + |V| \log|V|)$
Algoritmos

O algoritmo de Dijkstra, concebido pelo cientista da computação holandês Edsger Dijkstra em 1956 e publicado em 1959, soluciona o problema do caminho mais curto num grafo dirigido ou não dirigido com arestas de peso não negativo, em tempo computacional O([m+n]log n) onde m é o número de arestas e n é o número de vértices. O algoritmo que serve para resolver o mesmo problema em um grafo com pesos negativos é o algoritmo de Bellman-Ford, que possui maior tempo de execução que o Dijkstra.

O algoritmo de Dijkstra assemelha-se ao BFS, mas é um algoritmo guloso, ou seja, toma a decisão que parece ótima no momento. Para a teoria dos grafos uma "estratégia gulosa" é conveniente já que sendo P um menor caminho entre 2 vértices U e V, todo sub-caminho de P é um menor caminho entre 2 vértices pertencentes ao caminho P, desta forma construímos os melhores caminhos dos vértices alcançáveis pelo vértice inicial determinando todos os melhores caminhos intermediários. Nota: diz-se 'um menor caminho' pois caso existam 2 'menores caminhos' apenas um será descoberto.

O algoritmo considera um conjunto S de menores caminhos, iniciado com um vértice inicial I. A cada passo do algoritmo busca-se nas adjacências dos vértices pertencentes a S aquele vértice com menor distância relativa a I e adiciona-o a S e então repetindo os passos até que todos os vértices alcançáveis por I estejam em S. Arestas que ligam vértices já pertencentes a S são desconsideradas.

Um exemplo prático do problema que pode ser resolvido pelo algoritmo de Dijkstra é: alguém precisa se deslocar de uma cidade para outra. Para isso, ela dispõe de várias estradas, que passam por diversas cidades. Qual delas oferece uma trajetória de menor caminho?

Algoritmo

• 1º passo: iniciam-se os valores:

para todo v ∈ V[G]
     d[v]← ∞ 
     π[v] ← nulo
d[s] ← 0

V[G] é o conjunto de vértices(v) que formam o Grafo G. d[v] é o vetor de distâncias de s até cada v. Admitindo-se a pior estimativa possível, o caminho infinito. π[v] identifica o vértice de onde se origina uma conexão até v de maneira a formar um caminho mínimo.

• 2º passo: temos que usar dois conjuntos: S, que representa todos os vértices v onde d[v] já contem o custo do menor caminho e Q que contem todos os outros vértices.

Q ← V[G]

• 3º passo: realizamos uma série de relaxamentos das arestas, de acordo com o código:

enquanto Q ≠ ø
         u ← extrair-mín(Q)
         S ← S ∪ {u}
         para cada v adjacente a u
              se d[v] > d[u] + w(u, v)          //relaxe (u, v)
                 então d[v] ← d[u] + w(u, v)
                       π[v] ← u

w(u, v) é o peso(weight) da aresta que vai de u a v.

u e v são vértices quaisquer e s é o vértice inicial.

extrair-mín(Q), pode usar um heap de mínimo ou uma lista de vértices onde se extrai o elemento u com menor valor d[u].

No final do algoritmo teremos o menor caminho entre s e qualquer outro vértice de G. O algoritmo leva tempo O(m + n log n) caso seja usado um heap de Fibonacci, O(m log n) caso seja usado um heap binário e O(n²) caso seja usado um vetor para armazenar Q.

Implementação em C/C++

Implementação em C utilizando uma matriz de adjacências. Dependendo da quantidade limite de vértices (MAXV) pode se tornar ineficiente quanto ao uso de memória, sendo recomendado usar uma lista de adjacências.

#include <string.h> //memset

// MAXV é uma constante que define a quantidade máxima de vértices
#define MAXV 100

// Matriz de adjacências
// Se MAdj[i][j] > 0, então há aresta que liga 'i' a 'j' com custo MAdj[i][j].
int MAdj[MAXV][MAXV];

// Armazena a distância mínima partindo de um vértice 'i' até todos os outros vértices
// dis[j] representa a menor distância de 'i' a 'j'.
int dis[MAXV];

// Calcula as distâncias de 'Vi' a todos os outros vértices de um grafo com 'V' vértices e armazena-as em dis[]
void dijkstra (int Vi, int V)
{
        // vis[i] informa se o vértice 'i' já foi visitado/analisado ou não (inicialmente nenhum vértice foi)
        char vis[MAXV];
        memset (vis, 0, sizeof (vis));

        // Inicialmente afirmamos que a menor distância encontrada entre Vi e qualquer outro vértice (exceto o próprio Vi) é infinita
        memset (dis, 0x7f, sizeof (dis));
        dis[Vi] = 0;

        while (1)
        {
                int i, n = -1;

                for (i = 0; i < V; i++)
                        if (! vis[i] && (n < 0 || dis[i] < dis[n]))
                                n = i;

                if (n < 0)
                        break;
                vis[n] = 1;

                for (i = 0; i < V; i++)
                        if (MAdj[n][i] && dis[i] > dis[n] + MAdj[n][i])
                                dis[i] = dis[n] + MAdj[n][i];
        }
}

Implementação em C++ utilizando uma lista de adjacências.

#include <string.h> //memset
#include <vector>

using namespace std;

// MAXV é uma constante que define a quantidade máxima de vértices
#define MAXV 100

// Lista de adjacências
// Para inserir uma aresta - partindo do vértice 'i' ao vértice 'j', com custo 'c' - na lista, podemos usar:
// LAdj[i].push_back (make_pair (j, c));
vector < pair <int, int> > LAdj[MAXV];

// Armazena a distância mínima partindo de um vértice 'i' até todos os outros vértices
// dis[j] representa a menor distância de 'i' a 'j'.
int dis[MAXV];

// Calcula as distâncias de 'Vi' a todos os outros vértices de um grafo com 'V' vértices e armazena-as em dis[]
void dijkstra (int Vi, int V)
{
        // vis[i] informa se o vértice 'i' já foi visitado/analisado ou não (inicialmente nenhum vértice foi)
        char vis[MAXV];
        memset (vis, 0, sizeof (vis));

        // Inicialmente afirmamos que a menor distância encontrada entre Vi e qualquer outro vértice (exceto o próprio Vi) é infinita
        memset (dis, 0x7f, sizeof (dis));
        dis[Vi] = 0;

        while (1)
        {
                int i, n = -1;

                for (i = 0; i < V; i++)
                        if (! vis[i] && (n < 0 || dis[i] < dis[n]))
                                n = i;

                if (n < 0)
                        break;
                vis[n] = 1;

                for (i = 0; i < LAdj[n].size (); i++)
                        // Aresta n -> LAdj[n][i].first com custo LAdj[n][i].second
                        if (dis[LAdj[n][i].first] > dis[n] + LAdj[n][i].second)
                                dis[LAdj[n][i].first] = dis[n] + LAdj[n][i].second;
        }
}

A implementação do algorítmo utilizando uma lista de adjacências é ligeiramente mais rápida que a implementação com uma matriz de adjacências para casos em que o número de arestas não se aproxima do pior caso (uma aresta ligando cada par de vértices); quando próximo ao pior caso, o desempenho é similar. Ambos possuem complexidade de tempo em torno de O(V²).

É possível obter uma solução em O(E log V) (sendo E o número de arestas) utilizando um heap de fibonacci (ou a priority queue da STL de C++) para extrair o vértice não-visitado com menor distância. O heap simples, embora levemente mais lento que o heap de fibonacci, também pode ser usado para obter uma complexidade similar.

Ver também

• Algoritmo de Bellman-Ford
• Algoritmo A*

Ligações externas

• Artigo explicativo sobre o algoritmo
• Artigo e Implementação do Algoritmo de Dijkstra em C
• (em espanhol) Algoritmo de Dijkstra em C
• (em inglês) Algoritmo de Dijkstra em C#
• (em inglês) [1] - NIST
• (em inglês) Applet do algoritmo de Dijkstra