Требуется разработать программу на C# Windows Forms, которая позволяет решить задачу отыскания кратчайшего пути между любой парой вершин ориентированного графа с помощью алгоритма Дейкстра.
Требования к программе:
– количество вершин графа вводится пользователем и заранее неизвестно (не более 10);
– граф задаётся матрицей инцидентности, которая также выполняет роль матрицы весов; в графе не должно быть циклов с отрицательным весом;
– вершины, между которыми ищется кратчайший путь, задаются пользователем и заранее неизвестны;
– для заданной пары вершин программа должна либо отыскать кратчайший путь между ними и при этом выдать длину пути и список вершин, через которые проходит кратчайший путь ((необходимо также выделить путь на графе), либо выдать сообщение, что пути между вершинами не существует.
Требования к интерфейсу:
Необходимо предусмотреть две возможности задания графа и внесения корректировок в него:
– с помощью матрицы инцидентности, которая доступна пользователю для заполнения и редактирования;
– непосредственно с помощью набора операций над вершинами и дугами графа, которые вызываются по событиям, связанным с щелчками мыши или нажатием клавиш.
Например, нажатие правой клавиши мыши в той части экрана, в которой выведен граф, приводит к появлению контекстного меню, пункты которого позволяют:
– добавить вершину в граф;
– добавить дугу;
– удалить вершину;
– удалить дугу;
– изменить вес дуги.
Требуется также предусмотреть возможность перетаскивания вершин графа, а также задания исходной и конечной вершин путем их выбора с помощью мыши. Обеспечить сохранение матрицы инцидентности в файле и возможность ее последующей загрузки из файла с построением соответствующего графа.
