Algoritmo per trovare la rotta commerciale ottimale (ciclo negativo con costo più basso per spigolo in un digramma)

Dato il seguente problema (una descrizione leggermente semplificata del trading nel gioco per computer Escape Velocity: Nova ( mappa di sistema )):

• Dato un insieme di sistemi (solari).
• Ogni sistema è collegato da una rotta di viaggio dell'iperspazio a uno o più altri sistemi; ogni rotta collega due sistemi.
• Fare un salto iperspaziale ha un costo in dollari (che copre i costi del carburante). Il costo è lo stesso indipendentemente dal salto che stai facendo.
• Ogni sistema ha un centro commerciale con vari prodotti (cibo, metallo, attrezzature, ecc.) disponibili per il commercio ad un determinato prezzo. Il prezzo varia tra i sistemi.
• Per semplificare, diremo che puoi tenere una sola unità di una singola merce in un dato momento.
• Una rotta commerciale è una serie di salti iperspaziali che iniziano e finiscono nello stesso sistema (un ciclo), comprando e vendendo merci lungo la strada.
• Il profitto di una rotta commerciale è definito come profitto ottenuto comprando e vendendo merci lungo la strada meno il costo totale dei salti iperspaziali realizzati.

Voglio essere in grado di rispondere a domande come le seguenti:

1. Qual è la rotta commerciale più redditizia?
2. Qual è la rotta commerciale più redditizia che inizia e finisce in un sistema specifico?
3. Qual è la rotta commerciale più redditizia che coinvolge meno di X salti?
4. Qual è la rotta commerciale più redditizia che coinvolge meno di X salti che iniziano e finiscono in un sistema specifico?

Ho intenzione di modellarlo come un digrafo:

1. Ogni sistema è un vertice.
2. Per ogni percorso di viaggio dell'iperspazio aggiungi due spigoli (uno in ogni direzione) che collegano i due vertici con un peso uguale al costo di un salto iperspaziale.
3. Per ogni sistema
   • per ogni merce disponibile in quel sistema
     • per ogni sistema in cui il prezzo della merce è inferiore a quello del sistema corrente (non otterremo mai un profitto se il costo alla destinazione è più alto, quindi omettiamo quei bordi)
       • aggiungi un bordo dal sistema corrente a quel sistema con il peso di (number of jumps to reach that system) * (cost per jump) - (difference in price of the commodity) (vale a dire il profitto che deve essere ottenuto acquistando nel sistema corrente e vendendo nel sistema di destinazione)

Credo che la descrizione tecnica di ciò che sto cercando sia (per la domanda 1): dato il digrafo precedente qual è il ciclo negativo con il più basso costo medio per spigolo.

Mi rendo conto che posso usare una ricerca in ampiezza per rispondere alle domande 3 e 4 a condizione che il numero massimo di salti sia abbastanza piccolo da non esaurire la memoria, ma sospetto che non sia pratico rispondi 1 o 2 in questo modo.

Ho letto il capitolo Risolvi problemi cercando in AI: un approccio moderno ma, per quanto posso dire, gli algoritmi richiedono pesi di bordo positivi.

Un po 'di Google su Google mi ha trovato l'algoritmo Bellman-Ford e mentre ciò supporta il margine negativo la mia comprensione è che non fornisce costi accurati quando sono coinvolti cicli negativi.

Ci sono degli algoritmi che posso usare per risolvere questo problema in modo più efficiente?