## `Network::shortPath` -- shortest paths from one single node

#### Introduction

``Network::shortPath`(G, v)` returns a table with the length of shortest paths from `v` to all other nodes in the network with respect to the edge weight.

``Network::shortPath`(G, v, w)` gives the length of a shortest path from `v` to `w`.

#### Call(s)

`Network::shortPath(G, v <, w> <, Length> <, Path>)`

#### Parameters

`G` | - | network
`v, w` | - | nodes in the network

#### Options

`Length` | - | include table of path lengths; this is the default case, if Path is not given.
`Path` | - | return table of paths

#### Returns

a number, a table or a sequence of two tables.

#### Details

- If the optional argument `Path` is given, then a table with shortest pithes is returned.
- If `Length` and `Path` are given, then both the length of the shortest paths and the paths are returned.

#### Example 1

    >> V := [1, 2, 3, 4, 5]:
       Vw := [25, 0, 0, 0, -25]:
       Ed := [[1, 2], [1, 3], [2, 3],
              [2, 4], [3, 4], [3, 5], [4,  5]]:
       Ew := [7, 6, 5, 4, 2, 2, 1]:
       Ecap := [30, 20, 25, 10, 20, 25, 20]:
       N1 := Network(V, Ed, Eweight=Ew, Capacity=Ecap, Vweight=Vw):

    >> Network::shortPath(N1,1)

                                     table(
                                       5 = 8,
                                       4 = 8,
                                       3 = 6,
                                       2 = 7,
                                       1 = 0
                                     )

    >> Network::shortPath(N1,1,Path)

                                 table(
                                   5 = [1, 3, 5],
                                   4 = [1, 3, 4],
                                   3 = [1, 3],
                                   2 = [1, 2]
                                 )

#### Background

- If there are only non-negative edge weights the algorithm of Dijkstra is used. If there are positive and negative edge weights the algorithm of Bellman is used.

#### Changes

- used to be called `Network::ShortPath`

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000