É 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.

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.