Mostrar código-fonte de Algoritmo de Dijkstra

{{mais notas|data=Agosto de 2013}}
{{Info/Algoritmo
|classe       =[[Algoritmo de busca]]
|imagem       =[[Imagem:Dijkstra Animation.gif|Execução do algoritmo de Dijkstra]]
|estrutura    =[[Grafo]]
|data         =
|pior_caso    =<math>O(|E| + |V| \log|V|)</math>
|melhor_caso  =
|complexidade =
|otimo        =
|estabilidade =
}}
O '''algoritmo de Dijkstra''', concebido pelo [[Ciência da computação|cientista da computação]] holandês [[Edsger Dijkstra]] em 1956 e publicado em 1959,<ref name="Dijkstra Interview">{{citar periódico|último =Dijkstra|primeiro =Edsger|autor2=Thomas J. Misa, Editor|título=An Interview with Edsger W. Dijkstra|periódico=Communications of the ACM|data=agosto de 2010|volume=53|número=8|páginas=41–47|citação=What is the shortest way to travel from Rotterdam to Groningen? It is the algorithm for the shortest path which I designed in about 20 minutes.  One morning I was shopping with my young fianceé, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path.|doi=10.1145/1787234.1787249}}</ref><ref>{{harvnb|Dijkstra|1959}}</ref> soluciona o [[problema do caminho mais curto]] num [[grafo dirigido]] ou não dirigido com arestas de peso não negativo, em tempo computacional <math>O(E + V \log(V))</math> onde V é o número de vértices e E é o número de arestas. 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 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 de 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 de Dijkstra ==

* '''1º passo:''' iniciam-se os valores:

 para todo v ∈ V[G]
      d[v] ← ∞
      π[v] ← -1
 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 o conjunto ''Q'', cujos vértices ainda não contém o custo do menor caminho d[v] determinado.

 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)                     //Q ← Q - {u}
          para cada v adjacente a u
               se d[v] > d[u] + peso(u, v)          //relaxe (u, v)
                  então d[v] ← d[u] + peso(u, v)
                        π[v] ← u

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

u e v são vértices quaisquer e s é o vértice inicial.
ffd
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.

O algoritmo de Dijkstra é um exemplo de [[algoritmo guloso]] que gera a solução ótima em tempo polinomial.

=== Exemplo de código em c++ ===
<syntaxhighlight lang="c++" line="1">
// Implementação do algoritmo de Dijkstra
// Teste: http://br.spoj.com/problems/ENGARRAF/

#include <iostream>
#include <list>
#include <queue>
#define INFINITO 10000000

using namespace std;

class Grafo
{
private:
	int V; // número de vértices

	// ponteiro para um array contendo as listas de adjacências
	list<pair<int, int> > * adj;

public:

	// construtor
	Grafo(int V)
	{
		this->V = V; // atribui o número de vértices

		/*
			cria as listas onde cada lista é uma lista de pairs
			onde cada pair é formado pelo vértice destino e o custo
		*/
		adj = new list<pair<int, int> >[V];
	}

	// adiciona uma aresta ao grafo de v1 à v2
	void addAresta(int v1, int v2, int custo)
	{
		adj[v1].push_back(make_pair(v2, custo));
	}

	// algoritmo de Dijkstra
	int dijkstra(int orig, int dest)
	{
		// vetor de distâncias
		int dist[V];

		/*
		   vetor de visitados serve para caso o vértice já tenha sido
		   expandido (visitado), não expandir mais
		*/
		int visitados[V];

		// fila de prioridades de pair (distancia, vértice)
		priority_queue < pair<int, int>,
					   vector<pair<int, int> >, greater<pair<int, int> > > pq;

		// inicia o vetor de distâncias e visitados
		for(int i = 0; i < V; i++)
		{
			dist[i] = INFINITO;
			visitados[i] = false;
		}

		// a distância de orig para orig é 0
		dist[orig] = 0;

		// insere na fila
		pq.push(make_pair(dist[orig], orig));

		// loop do algoritmo
		while(!pq.empty())
		{
			pair<int, int> p = pq.top(); // extrai o pair do topo
			int u = p.second; // obtém o vértice do pair
			pq.pop(); // remove da fila

			// verifica se o vértice não foi expandido
			if(visitados[u] == false)
			{
				// marca como visitado
				visitados[u] = true;

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

				// percorre os vértices "v" adjacentes de "u"
				for(it = adj[u].begin(); it != adj[u].end(); it++)
				{
					// obtém o vértice adjacente e o custo da aresta
					int v = it->first;
					int custo_aresta = it->second;

					// relaxamento (u, v)
					if(dist[v] > (dist[u] + custo_aresta))
					{
						// atualiza a distância de "v" e insere na fila
						dist[v] = dist[u] + custo_aresta;
						pq.push(make_pair(dist[v], v));
					}
				}
			}
		}

		// retorna a distância mínima até o destino
		return dist[dest];
	}
};

int main(int argc, char *argv[])
{
	Grafo g(5);

	g.addAresta(0, 1, 4);
	g.addAresta(0, 2, 2);
	g.addAresta(0, 3, 5);
	g.addAresta(1, 4, 1);
	g.addAresta(2, 1, 1);
	g.addAresta(2, 3, 2);
	g.addAresta(2, 4, 1);
	g.addAresta(3, 4, 1);

	cout << g.dijkstra(0, 4) << endl;

	return 0;
}
</syntaxhighlight><ref>{{Citar web |ultimo=262588213843476 |url=https://gist.github.com/marcoscastro/d4e0df5b134c2cd63cf2 |titulo=Programação em C++ - Algoritmo de Dijkstra |acessodata=2021-08-13 |website=Gist |lingua=en}}</ref>

== Problemas relacionados ==
O algoritmo de Dijkstra não consegue encontrar o menor caminho em um grafo com pesos negativos. Para esse propósito, pode-se usar o [[algoritmo de Floyd-Warshall]], que consegue descobrir a menor distância entre todos os pares de vértices de qualquer grafo sem ciclos com peso negativo em uma complexidade de tempo O(V³). Se o problema não exigir o cálculo da distância entre todos os pares de vértices pode-se aplicar o algoritmo de Bellman-Ford, com complexidade de tempo O(V*E).
Em uma árvore, é possível encontrar a distância entre um vértice inicial e todos os outros vértices em tempo O(V+E), utilizando [[busca em profundidade]] (também conhecida como DFS). Em um grafo cujas arestas têm todas o mesmo peso, pode-se encontrar a distância entre um vértice inicial e todos os outros vértices, para um grafo qualquer, em O(V+E), utilizando [[busca em largura]] (também conhecida como BFS).
O processo utilizado no algoritmo de Dijkstra é bastante similar ao processo usado no [[algoritmo de Prim]]. O propósito deste último, entretanto, é encontrar a [[árvore geradora mínima]] que conecta todos os nós de um grafo. O BFS pode ser visto como um caso especial do algoritmo de Dijkstra em grafos não dirigidos, onde a fila de prioridade assume o comportamento [[FIFO]].

== Ver também ==
* [[Algoritmo de Floyd-Warshall]]
* [[Algoritmo de Bellman-Ford]]
* [[Algoritmo A*]]
* [[Busca em profundidade]]
* [[Busca em largura]]

{{Referências}}

== Ligações externas ==
* [http://www.inf.ufsc.br/grafos/temas/custo-minimo/dijkstra.html Artigo explicativo sobre o algoritmo]
* [http://www.vivaolinux.com.br/script/Algoritmo-de-Dijkstra Artigo e Implementação do Algoritmo de Dijkstra em C]
* {{((en))}} [https://web.archive.org/web/20071012044440/http://www.codeproject.com/useritems/Shortest_Path_Problem.asp Algoritmo de Dijkstra em C#]
* {{((en))}} [http://optlab-server.sce.carleton.ca/POAnimations2007/DijkstrasAlgo.html Simulação do algoritmo de Dijkstra]
{{controle de autoridade}}

[[Categoria:Algoritmos de grafos|Dijkstra]]
[[Categoria:Algoritmos de busca]]
[[Categoria:Edsger Dijkstra]]