Come posso trovare il percorso più breve tra due sottografi di un grafico più grande?

6

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 su Wikimedia e ho attinto, non è il mio vero problema.)

    
posta Pops 23.08.2014 - 21:51
fonte

2 risposte

4

Dovresti essere in grado di adattare l'algoritmo di Dijkstra.

Aggiungi solo due punti A & B al tuo grafico, che sono collegati a uno dei sottografi ciascuno. Quindi calcola il percorso più breve tra i due punti A & B.

Il percorso più breve tra i due sottotitoli dovrebbe essere il percorso che si ottiene dopo aver rimosso A & B dal risultato.

    
risposta data 23.08.2014 - 22:50
fonte
1

Dopo aver lottato per un giorno cercando di infilare nodi e spigoli finti nel mio codice mal progettato, sto iniziando a pensare che il suggerimento di SJuan76 sia davvero molto elegante. Non riesco a dimostrare che funzioni in tutti i casi, ma ho eseguito alcuni esempi a mano e sembra che vada bene.

Inizia con il vecchio Algoritmo di Dijkstra . Apporta le seguenti modifiche minori:

  • L'algoritmo regolare imposta tutte le distanze iniziali su infinito diverse da "il nodo di origine". Invece, imposta tutte le distanze iniziali all'infinito. Quindi, modifica la distanza a zero per ciascun nodo nel sottografo "inizio". (Per un grafico non orientato come il mio, puoi semplicemente selezionare entrambi i sottografi.)

  • Continua a eseguire l'algoritmo normalmente fino a quando gli unici nodi che rimangono nel set non visitato sono nodi nel sottografo "fine". È sicuro fermarsi a questo punto perché possono solo probabilmente fare distanze maggiori, non più piccole. (Se si hanno pesi negativi, questo non si applica.)

  • Guarda tutti i nodi nel sottotitolo "fine" e scegli quello che ha il punteggio totale più basso. Questo è il nodo finale.

  • Segui il percorso delle informazioni "nodo precedente" salvate fino a quando non viene raggiunto un nodo nel sottografo "inizio".

risposta data 25.08.2014 - 01:31
fonte

Leggi altre domande sui tag