Útvonal ellenőrzése mátrixban

Internet: PHP, CGI, stb.

Sziasztok,

keresek libet akár JS, akár PHP, de nemigazán találok ilyet (igazából nem is nagyon tudom, miképp nevezhetik ezt).
A feladat az volna, hogy egy adott mátrix bármely pontjáról meg lehessen állapítani, hogy kapcsolatban van-e a másikkal. Szemléltetem :)

__123456789
___________
A|100100110
B|110101100
C|011111000
D|100001000

Azaz A1 összeköttetésben van-e mondjuk A4-el és D6-al.
Remélem érthető így a példa.:)
Valamiféle útvonaltervezés szerűre lenne szükség, de amiket találtam, azok szinte mind valami Google maps-es dolog koordinátákkal, nekem viszont egy ilyen mátrix a forrásom, nem térkép.

Előre is köszönöm a segítséget!

  • 4732 megtekintés

( handler | 2014. 06. 21., szo – 10:30 )

Amit keresel, azt ugy hivjak, hogy transitive closure. A transitive closure szamitasa megoldhato Floyd-Warshall algoritmussal (n^3), Coppersmith–Winograd matrix szorzassal (n^2.376).

Nuutila, E., Efficient Transitive Closure Computation in Large Digraphs. Acta Polytechnica Scandinavica, Mathematics and Computing in Engineering Series No. 74, Helsinki 1995, 124 pages. Published by the Finnish Academy of Technology. ISBN 951-666-451-2, ISSN 1237-2404, UDC 681.3.

https://stackoverflow.com/questions/3517524/best-known-transitive-closu…
http://www.tankonyvtar.hu/hu/tartalom/tamop425/0046_adatstrukturak_es_a…