Zastosowanie Algorytmu Dijkstry

Witam! Mam do zrobienia program który będzie wyszukiwał najkrótsze i najtańsze połączenia (powiedzmy że lotnicze) pomiędzy miastami. W programie ma być też możliwość dodania kolejnego miasta i jego powiązanie z pozostałymi. Zakładamy że cena połączeń pomiędzy miastami jest sumą cen lotów do każdego z tych miast. Mam to zrobić w taki sposób, że dla MIAST i POŁACZEŃ mają być stworzone klasy. Na pytanie o pomoc prowadzący powiedział mi że mogę skorzystać z Algorytmu Dijkstry. I tu pojawia się moje pytanie: jak to ugryźć z tej strony? Moim zdaniem najłatwiej byłoby zrobić dwie tablice dwuwymiarowe i w ten sposób przedstawić graf, mam jednak to zrobić klasami i totalnie nie mam pomysłu co ma się w tych klasach znaleźć i jak to połączyć z Dijkstrą. Myślałem o tym, żeby w klasie MIASTO zawrzeć godziny przylotu na dane lotnisko i odlotu (zrobić to godzinami, nie odległosciami pomiędzy poszczególnymi miastami), nazwe lotniska na które przylatujemy i tego z którego lecimy, a w klasie POŁĄCZENIE cenę tych połączeń, ale nadal nie umiem tego połączyć z Dijkstrą. Jakieś pomysły?

A nie chodzi tu przypadkiem o dodanie w klasie po prostu wektora połączeń z miastami i przypisanie tym połączeniom odległości i ceny ? Następnie algorytmem wyszukać po odległości, a później po cenie. Dodawanie nowych miast/połączeń też nie powinno sprawić problemu.