Пример 1

Маленький график, который будет использоваться для алгоритмов:

G := Graph([a, b, c, d], [[a, b], [a, c], [b, c], [c, d]], 
           EdgeWeights = [2, 1, 3, 2],
           EdgeCosts = [1, 3,1, 2],
           Directed):

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

Graph::shortestPathAllPairs(G)

Интерпретация таблицы следующие:

Первая таблица содержит каждый путь: (FromVertex, ToVertex) = вес/стоимость. Вторая таблица немного более хитра. Левая сторона снова является самим путем. На правой стороне, хотя, вершина, которая была найдена перед итоговой вершиной, была достигнута, утверждается. Если, например, путь от a до d должен быть найден со всеми вершинами, которые используются в этом пути, это сделано следующим образом: Сначала возьмите сам путь (a, d). Предшественником является c. Теперь взгляните для пути (a, c). Это - предшественник, a. Поскольку предшественник равняется первой вершине в пути, который будет найден, поиск закончен и путь, которым найден a -> c -> d. Чтобы искать график затраты опция, SearchFor=Costs должен быть добавлен.

Graph::shortestPathAllPairs(G, SearchFor = Costs)

Пример 2

Теперь веса графика изменяются, так, чтобы был присвоен отрицательный вес ребра. Вы будете видеть, что это не влияет на правильность результатов, которые алгоритм возвращает (как, например, Дейкстра).

G := Graph([a, b, c, d], [[a, b], [a, c], [b, c], [c, d]], 
           EdgeWeights = [2, 1, 3, 2],
           EdgeCosts = [1, 3,1, 2],
           Directed):

G := Graph::setEdgeWeights(G, Graph::getEdges(G), [2, 1, -3, 2]):

Graph::shortestPathAllPairs(G)

Возвращаемые значения

Перечислите состоящий из двух таблиц. Первая таблица содержит сумму весов пути или затраты и второе предшественники для каждого пути (чтобы найти полный путь).