Sto lavorando con una multigrafia ponderata e non orientata (i loop non sono permessi, la maggior parte delle connessioni di nodo ha molteplicità 1, alcune connessioni di nodo hanno molteplicità 2). Devo trovare il percorso più breve tra due sottografi di questo grafico che non si sovrappongono l'uno con l'altro. Non ci sono altre restrizioni su quali nodi dovrebbero essere usati come punti iniziali / finali.
I bordi possono essere selettivamente rimossi dal grafico in determinati momenti (come spiegato in la mia domanda precedente ) quindi è possibile che per due sottografi dati, non ci sia alcun modo per collegarli.
Sono abbastanza sicuro di aver già sentito parlare di un algoritmo, ma non riesco a ricordare come si chiama e il mio Google cerca stringhe come "il percorso più breve tra i sottografi" non ha aiutato. Qualcuno può suggerire un modo più efficiente per farlo rispetto al confronto tra i percorsi più brevi tra tutti i nodi in un sottografo con tutti i nodi nell'altro sottografo? O almeno dimmi il nome dell'algoritmo in modo che possa cercarlo da solo?
Ad esempio, se ho il grafico sottostante, i nodi cerchiati in rosso potrebbero essere un sottografo ei nodi cerchiati in blu potrebbero essere un altro. I bordi avranno tutti pesi interi positivi, sebbene non siano mostrati nell'immagine. Vorrei trovare qualsiasi percorso abbia il costo totale più breve purché inizi su un nodo rosso e finisca su un nodo blu. Credo che questo significhi che le specifiche posizioni dei nodi e pesi degli spigoli non possono essere ignorati.
(Questoèsolounesempiodigraficochehoafferrato