Программа  14                        Кирсанов М.Н, 
Графы в Maple

 

Минимальный путь

>    restart: with(networks):

>    new(G):  n:=6:

>    addvertex(i$i=1..n,G); # Вершины исходного графа

1, 2, 3, 4, 5, 6

>    addedge([seq([i,i+3],i=1..3),[1,2],[2,3],[4,5],[5,6],[1,5]],

>    weights=[12,16,20,11,15,13,14,26],G):# Ребра и веса графа

>    draw(Linear([1,4],[2,5],[3,6]),G);   

[Maple Plot]

>    T := shortpathtree(G,1): # Дерево минимальных путей

>    W:=vweight(T);           # Таблица весов (расстояний)

W := TABLE(sparse,[1 = 0, 2 = 11, 3 = 26, 5 = 25, 4 = 12, 6 = 39])

>    draw(T);       # Рисунок дерева

[Maple Plot]

>    MinPath:=W[6]; # Ответ. Минимальный путь 1 - 6

MinPath := 39

>    allpairs(G)[1,6]; # Другой способ решения задачи

39