Dado um gráfico cíclico direcionado em que o peso de cada aresta pode ser negativo, o conceito de "caminho mais curto" só faz sentido se não houver ciclos negativos e, nesse caso, você pode aplicar o algoritmo de Bellman-Ford.
No entanto, estou interessado em encontrar o caminho mais curto entre dois vértices que não envolvam ciclismo (ou seja, sob a restrição de que você não pode visitar o mesmo vértice duas vezes). Este problema está bem estudado? Uma variante do algoritmo Bellman-Ford pode ser empregada? Caso contrário, existe outra solução?
Também estou interessado no problema equivalente de pares, para o qual, de outra forma, poderia aplicar Floyd – Warshall.