Talán, ha irányítom a gráfot, akkor lehet, hogy közelebb jutok a megoldáshoz:
irányított gráf esetén persze több legrövidebb út is lehetséges. (mármint több "a" és "b" között).
mivel egy általános gráfról van szó, ezért ez tartalmazhat kört is. az irányítás csak extra.
biztos, hogy van olyan a->b legrövidebb út, ami egy kör kerületi szakasza.
akkor veszem a b->a irányított utat, ami tuti hogy hosszabb, mint az a->b, mivel több csúcsát is tartalmazza a gráfnak
biztos, hogy marad ki lehetséges él, amivel még bővíthető ez a maximális út, ezért a visszirányú körből kimaradt csúcsokkal próbálom bővíteni a már létező b->a->b kört, aminek a végén az a->b élet elhagyva egy körmentes leghosszabb út az eredmény.
vagy nagyon nyakatekert és logikátlan?
/mazursky
Love your job but never love your company!
Because you never know when your company stops loving you!