Программа 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