Блог от AS3Coder'a о JavaScript, HTML, CSS... и немного о Flash.

четверг, 15 октября 2009 г.

Алгоритм Дейкстры на 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);
Вот и всё :)

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

11 комментариев:

  1. Немного поправить описание можно, мелочь: в описании getDijkstraPath, а в коде getDijkstra.
    И ещё то, что он учитываются направления графов. То бишь их в обе стороны надо задавать.

    ОтветитьУдалить
  2. Спасибо, за сообщение о недочетах :) Поправлю

    ОтветитьУдалить
  3. Есть вопрос по поводу производительности твоей реализации :) поискал на блоге, никаких способов для связи с тобой не нашел.
    Если есть интерес пообщаться по поводу этого алгоритма и его производительности, skype : nicolas.prof

    ОтветитьУдалить
  4. Над производительностью алгоритма я не работал :) Не стояло такой задачи. Просто написал по-быстрому смотря в блок схему курсовой работы. А для связи: as3coder@gmail.com

    ОтветитьУдалить
  5. Огромное спасибо, весьма доходчиво когда на деле и на 100% то, что нужно для текущей задачи, восторг!

    ОтветитьУдалить
  6. Farid, мог бы выложить полный код программы.
    Интересно как написан UI, только начинаю изучать это технологию и нет ни малейшего представления как это можно сделать (

    Был бы очень благодарен!

    ОтветитьУдалить
  7. Этот комментарий был удален автором.

    ОтветитьУдалить
  8. "Казалось бы задача решена, но, при попытке скомпилировать пример..." ©
    В коде упущено function Vertex (name:String) { edges = []; this.name = name; }
    И в GraphMethods как в тексте расхождение: метод "getDijkstra" вместо "getDijkstraPath".

    ОтветитьУдалить
  9. Хороший пример.
    soniko , с вашими правками работает,
    но метод "getDijkstra" с теми входными данными, что показаны в примере возвращает вершины v4 и v3,
    а v1 не возвращает. Одна вершина
    где-то теряется.
    И по идее хорошо бы возвращать ребра по которым прошел кратчайший путь. Тогда его легче будет перекрасить в другой цвет например и
    показать в программе вот он путь.

    ОтветитьУдалить
  10. Спасибо за классы, полезная штука.

    ОтветитьУдалить
  11. Спасибо за классы. Полезная штука.

    ОтветитьУдалить

Можно использовать некоторые HTML-теги, например <b>, <i>, <a>

Поиск по блогу

Обо мне



Farid Shamsutdinov (AS3Coder)
Russia, Tatarstan, Kazan
as3coder@gmail.com

Подробнее...

Постоянные читатели

© 2014 Farid Shamsutdinov. При копировании материалов, ссылка на источник обязательна. Технологии Blogger.