An application as course project for Technical University of Sofia that visualizes the work of Dijkstra's algorithm for finding the shortest path in a graph
Настолното приложение ще предоставя модерен графичен интерфейс за работа (Windows Forms). Приложението ще визуализира работата на алгоритъма на Дейкстра, известен още като алгоритъм за намиране на най-къси пътища в граф, решава проблема с намирането на най-краткия път от точка (пр. A) в графа до дадена дестинация (пр. точка F) при неотрицателни тегла на ребрата. Това е алчен алгоритъм, който по същина е подобен на алгоритъма на Прим. В реалната практика може да представлява намирането на най-късия маршрут до даден град както и намира приложение в GPS устройствата с цел оптимизация на транспорта.
Описание на алгоритъма: Подобно на Прим, генерираме SPT (shortest path tree) с даден източник като корен. Поддържат се два сета, един сет, който ще съдържа върховете, включени в дърво на най-късият път, а другият сет включва върхове, които все още не са включени в дървото. Основната идея на алгоритъма е релаксация: във всеки момент от работата му за всеки връх се пази информация за най-късия път, намерен до момента; ако след това алгоритъмът намери по-добър път, тази информация се актуализира.
Описание на програмата: Интерфейсът ще бъде разделен визуално на 3 блока. Представям накратко работата на всеки един от трите блока:
Първият блок ще представлява панел с команди за избор от потребителя – задаване на първоначално ид (начален връх) за започване на алгоритъма, бутон за стартиране на самия алгоритъм, бутон за добавяне на табове (работно поле, намиращо се във втория блок на програмата) и бутон за затваряне на текущ таб като ще има възможност за задаване на максимален брой отворени табове (полета), където може да бъдат конструирани самите графове, бутон за изтриване на текущия граф. Обмислям да има и слайдер, с който да може да се регулира скоростта на изпълнение на алгоритъма, но това ще определя по време на работата по проекта.
Вторият блок ще съдържа същинското работно поле, където потребителят ще може да конструира даден граф, който всъщност би могъл да има върхове (първата буква на всеки град) и тегла (километри) между самите градове. Ще има възможност за изтриване на вече съществуващ върх и за добавяне съответно с десен и ляв бутон на мишката – за целта ще реализирам готовата библиотека System.Drawing и System.Drawing.Drawing2D. В програмата ще има възможност за определяне на максимален брой върхове на графа. В този блок ще бъде същинската визуализация на работата на алгоритъма.
Третият блок ще визуализира матрица от вече зададените стойности на тегловните коефициенти като потребителят ще има възможност да въвежда числови стойности (чрез еднократно кликане на левия бутон) на километрите между върховете на графа както и да намалява стойностите с десен бутон на мишката (декрементира). С цел предотвратяване получаването на примки ще бъде невалидно въвеждане на тегловен коефициент за един и същи върх (тоест диагоналът на матрицата – (1,1), (2,2), (3, 3), …). В този блок ще има и таб с логове, който ще съдържа най-краткото разстояние между всеки върх.
Информация за бъдещата реализация на приложението:
Главна функционалност:
- Интерфейс за работа с програмата – Windows Forms интерфейс с три форми: главен панел с команди за работа с програмата, съдържащ бутони и едно текстово поле за въвеждане на начален върх; панел с визуализация работата на алгоритъма; панел за промяна стойностите на тегловните коефициенти (в образуваната квадтратна матрица) и таб с логовете (резултати от изпълнението на алгоритъма)
Вътрешна реализация на проекта:
- Реализация на библиотека – Проектът ще бъде разделен на два по-малки проекта – главен проект със стартиращ клас StartUp и папка Visualization – класове отговарящи за реализацията на Windows Forms формата; библиотека Models, където ще бъдат класовете отговарящи за алгоритъма