Milyen eljárás szerint keresi meg például az iwiw a legrövidebb utat 2 felhasználó között?

Legyen A az induló user, B a cél user.

Én valami olyasmire tippelnék, hogy először megnézi, hogy A és B ismeri-e egymást. Aztán összegyűjteném A ismerőseit és megnézném, hogy A ismerősei közül ismeri-e valaki B-t. Aztán egyesével végiglépkedve A ismerősein, megvizsgálnám, hogy A ismerősének valamelyik ismerőse ismeri-e B-t. És ezt lehet folytatni, de tapasztalatom szerint az IWIW-en szinte mindenki mindenkitől maximum a 3. ismeretségen belül van :)

Remélem érthetően írtam le.

Erről mi tanultunk infon! (egyetemi szinten) operációkutatáson. Ha érdekel akkor adj egy e-mail címet s elküldöm az anyagot amiben leirta a tanárúr:)

(nagyon csiptem a tanárbát!)

Ja, megfogalmazni meg tudom :) Csak a megvalósítással lennének gondjaim :) Pedig valaha programozónak készültem volna :D

(Az első)

nem tűnik túl jónak... eléggé NP teljes lesz a probléma így, márpedig nem gondolkodik olyan sokat a gép.

A megvalósítás amúgy nagyon egyszerű lenne (elmondom én hogy oldalnám meg): felépítünk egy n-fát, melyben minden elemnek az ismerősei a gyerekek, és figyeli hogy egy adott elem ne kerüljön bele egynél többször (hogy körmentes maradjon). Illetve minden újabb mélységben megnézzük hogy megtalálható-e a keresett ember. A fa mélysége a lépések száma, az útvonal pedig egyértelműen kiolvasható.

Szélességi bejárás. Ne mondja nekem senki hogy nem túl jó... amúgy nem kell fát felépíteni, mert már rendelkezésünkre áll egy gráf.

Röviden a megvalósítás: csúcsra általános művelet az összes ismerősét berakjuk egy sorba (ami ugye FIFO adatszerkezet, azaz ami először belekerül, az jön ki belőle először), aztán megjelöljük hogy ez már volt, és vesszük a következőt a sorból ki és elvégezzük rá ugyanezt. Mindezt addig, amíg nem találjuk meg akit keresünk, és persze feljegyezzük milyen messze volt.