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