Алгоритм Дейкстры на ActionScript 3.0

Столкнулся на работе с графами. Необходимо было найти кратчайший путь в заданном графе между двумя вершинами. Для решения задачи решил использовать алгоритм Дейкстры.

Алгоритм Дейкстры - алгоритм находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Назван в честь изобретателя Эдсгера Дейкстры.

Поискал в гугле. Нашел вот этот вариант реализации алгоритма на Action Script. Казалось бы задача решена, но, при попытке скомпилировать пример, посыпались ошибки. Разбираться было некогда, пришлось писать самому :)

На сайте http://www.allbest.ru/ нашел курсовую работу "Программная реализация алгоритма Дейкстры (построение цепей минимальной длины)". Прочитав работу, немного поразмыслив, получилось следующее:



В итоге 4 класса:

1. Vertex.as - класс для описания вершин.
2. Edge.as - класс для описания связей.
3. Graph.as - класс для описания графа.
4. GraphMethods.as - статический класс с методами работы с графами. Пока только один метод getDijkstraPath(). Позже буду добавлять новые методы :)

graph.zip (3 Кб)

Как этим пользоваться?

Создаем вершины.

var vertex1:Vertex = new Vertex("v1");
var vertex2:Vertex = new Vertex("v2");
var vertex3:Vertex = new Vertex("v3");
var vertex4:Vertex = new Vertex("v4");
var vertex5:Vertex = new Vertex("v5");
...

Свяжем некоторые вершины, с указанием расстояния между ними.

var edge1:Edge = new Edge(vertex1, vertex3, 50);
var edge2:Edge = new Edge(vertex3, vertex4, 75);
var edge3:Edge = new Edge(vertex3, vertex5, 25)
...

Создаем граф.

var graph:Graph = new Graph();

Вершины и связи добавим на граф.

graph.addVertex(vertex1);
graph.addVertex(vertex2);
graph.addVertex(vertex3);
graph.addVertex(vertex4);
graph.addVertex(vertex5);
...
//
graph.addEdge(edge1);
graph.addEdge(edge2);
graph.addEdge(edge3);

Вычислим кратчайший путь от первой вершины до четвертой, используя алгоритм Дейкстры.

var path:/*Vertex*/Array = GraphMethods.getDijkstraPath(graph, vertex1, vertex4);

Вот и всё :)

Ссылки по теме:

• Алгоритм Дейкстры — Википедия
• Схема алгоритма Дейкстры