Legrövidebb utak keresése gráfokban

Algoritmusok

Sziasztok!

Dijkstra algoritmusát szeretném módosítani a következő problémára:
Adott egy súlyozott, irányítatlan gráf. Ebben a gráfban szeretném megkeresni bizonyos csúcspontok között a legrövidebb utakat olyan módon, hogy a csúcsok közötti utak ne tartalmazzanak előre meghatározott más csúcspontokat. Tehát az eljárás bemenete legyen például az (f1, f2, f3, f4, f5) ponthalmaz, tehát keresem ezen halmaz elemeiből képzett csúcspárok közti legrövidebb utakat a gráfban, azonban ez az út nem tartalmazhatja a bemeneti halmaz többi elemét. Azaz ha f1-f3 közötti legrövidebb utat keresem, akkor az f2, f4, f5 csúcspontokat nem szabad érinteni (csak ha tényleg nincs más megoldás).

Van már egy megoldásom, azonban az kissé számításigényes, ezért kérem a segítségetek.

Köszönöm előre is.

Üdv,
kormanyos

( mrceeka v | 2015. 05. 05., k – 17:21 )

És ha először kihagyod f2, f4 és f5 csúcspontokat a hozzájuk tartozó élekkel a gráfból? Ha így nincs megoldás, megnézed ezen csúcsok és élek benthagyásával, van-e..

Üdv,
Marci

( SzBlackY | 2015. 05. 05., k – 17:34 )

Azaz ha f1-f3 közötti legrövidebb utat keresem, akkor az f2, f4, f5 csúcspontokat nem szabad érinteni (csak ha tényleg nincs más megoldás).

Minden pont párra igaz, hogy az összes többin nem szabad átmenni? Akkor minden pontra futtass egy Dijkstra-t, aztán kiíratáskor nézd meg, hogy A és B között van-e él, ha van, akkor az, egyébként a Dijkstra eredménye (ha a háromszög egyenlőtlenség igaz a gráfodra, akkor egyébként a sima Dijkstra is ezt fogja adni).

BlackY
--
"en is amikor bejovok dolgozni, nem egy pc-t [..] kapcsolok be, hanem a mainframe-et..." (sj)

A hozzászólásom arra vonatkozott, hogy az eredeti specifikáció szerint CSAK speciális pontok vannak:

Tehát az eljárás bemenete legyen például az (f1, f2, f3, f4, f5) ponthalmaz

Ráadásul visszaadhat olyan útvonalat, ami átmegy a speckó pontokon, ha nincs más útvonal.

Ezen feltétel pedig pszeudókódban: 


if(graph(f1,f2) > 0) return [edge(f1, f2)];
t = dijkstra(f1, f2) /* reméljük, hogy t élek listáit tartalmazó (t1,t2) leképezés :) */
return t[f1,f2];

BlackY
--
"en is amikor bejovok dolgozni, nem egy pc-t [..] kapcsolok be, hanem a mainframe-et..." (sj)

( kerozoli v | 2015. 05. 05., k – 17:37 )

És megkérdezhetem ennek a feladatnak a megoldása minek kapcsán merült fel ?

( vilmos.nagy | 2015. 05. 05., k – 17:48 )

Szia!

Bellman-Ford?
Legjobb emlékeim szerint ott egy táblázatot töltögetsz, ahol az (x,y) mezőben lévő elem azt mondja meg, hogy az f1-fx pontpár között mennyi a legrövidebb, legfeljebb y hosszú út.
Ha megvan a táblázat, akkor az fx. oszlopának:
* az első sora megmondja, milyen hosszú az egy élből álló út - ha van, végtelen, ha nincs
* a második sora, hogy milyen hosszú a __legfeljebb__ két élből álló (ha van)
* ...

Üdv,
Vili

--
blogom

Mi alapján döntöd el, hogy melyik csúcspontokat szeretnéd „kizárni”?
Mert ez a fentiekből nem derül ki. Ahogy látom, a többieknek sem tiszta.
Nekem az jött le onnan, hogy a lehető legkevesebb csúcsot tartalmazó utat részesíted előnyben - erre pedig a Bellman-Ford megoldás.
--
blogom

A kérdés nem arra irányult, hogy a lehető legkevesebb csúcsú utat keressem meg. A Ford-Bellman valóban ebből a szempontból remek választás lenne.
A bemeneti gráf néhány csúcspontjának strukturális szempontból speciális relevanciája van a többi csúcsponthoz képest. A lényeg az, hogy ezen speciális jelentőségű pontok között megtaláljam a gráfban azt a lehető legrövidebb utat, ami nem tartalmaz más speciális pontot. Legyenek például az f1, f2, f3, f4, f5 pontok ezek speciális csúcsok, ezeken kívül még van számos más egyéb csúcs is, amelyek nem kitüntetettek. Keresem az például az f1 és f5 csúcsok közötti legrövidebb utat. Ha ezen szerepel más speciális csúcs a kezdő és végponton kívül, akkor az ekvivalens azzal, mintha nem találtunk volna utat. Tehát arra a legrövidebb útra lenne szükségem ezen speciális csúcspárok között a gráfban, ami nem tartalmaz speciális pontokat, azaz csak "hagyományos" csúcsok fekszenek rajta. Az sem baj, ha hosszabb, mint a tényleges legrövidebb - de speciális pontokat tartalmazó - út.

https://youtu.be/EmMo7aTxInc?t=1m38s

szerk.: 3 Dijsktra?
Elsőnek úgy, hogy kiveszem belőle az összes speciális csúcsot (meg az azokból induló éleket), kivéve a start, s végpontot.
Másodjára úgy, hogy csak a speciális csúcsok közötti éleket veszem ki. (ugyancsak kivétel a kezdeti, s a végpont)
Harmadjára meg az eredeti gráfon.

Ha van út a speciális csúcsokon kívül, az első megtalálja.
Ha nincs, de elég egy speciális csúcsot érintenem (nem kell speciális csúcsból másik speciális csúcsba menni), akkor a második.
A harmadikhoz kell, hogy a speciális csúcsok között ne haladjon negatív súlyú él.
szerk2.: közben rájöttem, hogy nem lesz negatív él. bocs.
--
blogom

Hármat.
Egyet a 198 speciális csúcs nélkül.
Egyet a 198 speciális csúccsal, közbülső utak nélkül.
Egyet az eredeti gráfon.

Ha a 200 speciális csúcs között az összes lehetséges start-vég párra kelleni fog, az nem fog menni gyorsabban.

szerk.: jó, ezt be kéne látni, hogy nem fog menni gyorsabban. Egy pillanat.

szerk2.: Talán van.
Egy Floyd-dal csinálok egy mátrixot, ami bármely két pontpár között megmondja a legrövidebb utat. Ebből a mátrixból kell kettő:
* egy, amiben a speciális csúcsok között futó élek nincsenek benne
* egy, amiben azok is benne vannak

Utána minden speckó pontpárra (start-vég) elhagyom az összes többi speciális csúcsot. Dijsktraval keresek legrövidebb utat. Ha nyert, akkor győzelem. Ha nem, akkor a Floyd-ban benne van a megoldás.
Jó, ez még mindig egy Dijsktra minden speciális pontpárra - ami kurvasok.
De ha az összes speckó pontpár között kell út, akkor én a Floyd algoritmust próbálnám meg felokosítani, talán van rá esély.
--
blogom

( wauf | 2015. 05. 05., k – 18:26 )

Ha ismert az egy elre juto max suly (max_w), akkor minden f2, f4, f5-ot tartalmazo el sulyahoz hozza kell adni, lefuttatni egy A*-t/Dijkstrat, igy pont azt adja amit szeretnel. Aztan a legrovidebb ut sulyabol persze okosan le kell vonogatni a hozzaadott max_w-t, kulonos tekintettel arra az esetre, amikor ket "nem kedvelt" csucs ossze van kotve egymassal.

( Zsugabubus | 2015. 05. 05., k – 19:37 )

Ha a speciális csúcsokban O(1) a keresés ideje, akkor amikor egy csúcs szomszédai közt iterál a Dijkstra, egyszerűen megvizsgálnám, hogy benne van-e a speciális halmazban, és kihagynám.

Amennyiben ez a Dijkstra-algoritmus pszeudokódja:

1 function Dijkstra(Graph, source):
2
3 dist[source] ← 0 // Distance from source to source
4 prev[source] ← undefined // Previous node in optimal path initialization
5
6 for each vertex v in Graph: // Initialization
7 if v ≠ source // Where v has not yet been removed from Q (unvisited nodes)
8 dist[v] ← infinity // Unknown distance function from source to v
9 prev[v] ← undefined // Previous node in optimal path from source
10 end if
11 add v to Q // All nodes initially in Q (unvisited nodes)
12 end for
13
14 while Q is not empty:
15 u ← vertex in Q with min dist[u] // Source node in first case
16 remove u from Q
17
18 for each neighbor v of u: // where v is still in Q.
19 alt ← dist[u] + length(u, v)
20 if alt < dist[v]: // A shorter path to v has been found
21 dist[v] ← alt
22 prev[v] ← u
23 end if
24 end for
25 end while
26
27 return dist[], prev[]
28
29 end function

Akkor arra gondolsz, hogy a 18. sorban csak azokat a szomszédokat vegyem figyelembe, amik nem tiltottak? Mert ha igen, akkor ebben az esetben hogy fog rálépni a keresett út végpontjára? Mert ugye az is tiltott lesz.

Ezt most nem értem...miért lesz tiltott a végpont? Feltéve, ha nem tiltod ki szándékosan. De akkor meg nem lesz út egyáltalán oda.
Én arra gondoltam, hogy a 18 és 19 sor közé (pythonosan)
if v in tiltottak:
continue

Vagy arra gondolsz, hogy mi van, ha a tiltott csúcs nélkül nem lehet eljutni egyáltalán a célba? Akkor meg nem figyelmen kívül kell hagyni, hanem egy marha nagy súlyt adni ilyenkor az alt-hoz.
if v in tiltottak:
alt+=dist[u] + max_length
else
alt=dist[u] + length(u, v)

De lehet, hogy rosszul gondolom...

Szerk: elolvastam újra a feladatot, szóval a kezdő és a végpontot meg nyilván nem kell figyelembe venni a vizsgálatnál.

Arra gondoltam, hogy alapvetően minden speciális csúcs tiltott. Aztán minden aktuális iterációban "feloldunk" kettőt, amik között a legrövidebb utakat keressük. A Dijkstra megvalósításban pedig az algoritmus jellegéből adódóan nem tudod megoldani, hogy "feloldod" a végpontot, mivel a tiltott elemek listájában van.

Értem, most nézem, hogy a te algoritmusod kicsit más, mint amit én úgy 2 éve implementáltam :)
Te az összes csúcsot beteszed a queue-ba előre, de igazából elég a startot, és a tiéd az összes csúcsra megkeresi a legrövidebb utat, nem áll meg a célnál.

Itt nézd meg, Using a priority queue alatt:
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
(és alatta a kiegészítés)
Instead of filling the priority queue with all nodes in the initialization phase, it is also possible to initialize it to contain only source; then, inside the if alt < dist[v] block, the node must be inserted if not already in the queue (instead of performing a decrease_priority operation)

Ezt alkottam C++-ban régebben:
http://pastebin.com/x3m4g7sk
Hiányzik az Edge és a neighbors definíciója, de szerintem kitalálható, hogy mit is csinálnak ezek.