![[Maple Plot]](images/p153.gif)
Программа 15 Кирсанов М.Н,
Графы в Maple
Кратчайшее расстояние между вершинами
| > | restart:with(networks): |
| > | new(G):n:=6; |
| > | addvertex(i$i=1..n,G); |
n := 6
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); |
| > | T := shortpathtree(G,1): |
| > | W:=vweight(T): |
| > | MinPathFrom1to15:=W[6]; |
MinPathFrom1to15 := 39
| > | allpairs(G)[1,6]; |
39
Алгоритм поиска кратчайшего пути до всех вершин
| > | V:=Vector(1..n): |
| > | for i to n do V[i]:=infinity; od: |
| > | source:=1: target:=6: k:=source: V[k]:=0: U:=[0$3*n]: |
| > | flag:=false: |
| > | for i while not flag do |
| > | U[i]:=k: |
| > | d:=outdegree(k,G): |
| > | Nei:=departures(k,G): |
| > | for j from 1 to d do |
| > | CurrentW:=eweight(op(edges([k,Nei[j]],G)),G): |
| > | if((V[Nei[j]]=0) or (V[Nei[j]]>CurrentW+V[k])) then |
| > | V[Nei[j]]:=eweight(op(edges([k,Nei[j]],G)),G)+V[k]: end if; |
| > | end do; |
| > | Next:=n; |
| > | for j from 2 to n do |
| > | if not member(j,U) and V[j]<V[Next] then |
| > | Next:=j; |
| > | fi; |
| > | end do: |
| > | k:=Next; |
| > | flag:=is(k=target); |
| > | end do: |
| > | evalm(V); |
vector([0, 11, 26, 12, 25, 39])
| > | V[2];V[3];V[5]; |
| > | MinPathFrom1to15:=V[6]; |
11
26
25
MinPathFrom1to15 := 39
| > | departures(1,G); |
{2, 4, 5}
| > | outdegree(1,G); |
3