É um algoritmo de busca de caminho mínimo em um digrafo (grafo orientado ou dirigido) ponderado, ou seja, cujas arestas têm peso, inclusive negativo.
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.
Calcula os menores caminhos entre todos os pares de vértices usando programação dinâmica.
Método para calcular o fluxo máximo em uma rede de fluxo.
Algoritmo guloso que encontra uma árvore geradora mínima em um grafo conexo ponderado.
Constrói uma árvore geradora mínima expandindo a partir de um vértice inicial.
Percorre um grafo nível a nível a partir de um vértice origem, usando fila.
Explora o grafo avançando o máximo possível em um ramo antes de retroceder.
Consiste em determinar se é possível ou não fazer um passeio pela cidade começando e terminando no mesmo lugar, cruzando cada ponte exatamente uma única vez.