Дейкстра путь вес - PullRequest
       14

Дейкстра путь вес

1 голос
/ 10 августа 2011

Dijkstra

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

Ответы [ 2 ]

4 голосов
/ 10 августа 2011

Вы имеете в виду, что графическое представление graph не соответствует weight каждого пути?

У них тоже нет ... визуальное представление - это просто представление, больше ничего. Не должно быть эквивалентно весу.

Вы можете перерисовать график в любом случае, просто убедившись, что связи между вершинами сохранены.

Изменить: и не имеет значения, с каким графом вы имеете дело, будь то Дейкстра или любой другой. Вы можете даже найти графики, где направление имеет значение: от А до В вес может быть 10, а от В до А вес может быть 30. Нет проблем.

Редактировать 2 : изображение просто показывает, как вершины соединяются друг с другом. Изображение не должно быть в масштабе с графиком, который хранится в вашей программе. Иногда у вас будут графики с таким количеством вершин и ребер, что вы не сможете хорошо их представить. Для ваших задач программирования важны вершины, ребра и их вес. Изображение является лишь приблизительным представлением о нем. Вы можете перерисовать изображение по своему усмотрению, вам нужно просто указать все вершины, все ребра и все веса для каждого ребра.

2 голосов
/ 10 августа 2011

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

Это сбивает с толку, и вы можете сделать длину = вес, изменив способ построения графика.

...