Dostałem zadanie z którym nie mogę sobie poradzić. Może ktoś mi pomoże? Oto treść:
na płaszczyźnie dany jest zbiór punktów o współrzędnych całkowitych. Przez ścieżkę pomiędzy parą punktów tego zbioru rozumiemy sekwencję odcinków równoległych do osi ukł wsp. Długość ścieżki to suma długości odcinków wchodzących w jej skład. Ścieżka jest minimalna, jeśli nie istnieje krótsza ścieżka łącząca dana parę punktów. Minimalną ortogonalną siecią połączeń dla zadanego zbioru punktów płaszczyzny nazywamy taki zbiór odcinków, w kt każda para punktów ma połączenie minimalne i koszt całego zbioru (suma dł wszystkich punktów) jest minimalny.
należy wyznaczyć taką ścieżkę
Chciałbym zapytać czy ktoś ma pomysł na systematyczne rozwiązanie takiego zadania.
zadanie można reprezentować za pom grafu z wagami, ale nie umiem sformułować tego zadania w języku teorii grafów.