Previous Page Next Page Contents

Network::allShortPath -- shortest paths for all pairs of nodes

Introduction

Network::allShortPath(G) finds shortest paths in the network G.

Call(s)

Network::allShortPath(G <, Length> <, Path>)

Parameters

G - network

Options

Length - Return the lengths of shortest paths. This is the default unless Path is given.
Path - Return a table of shortest paths.

Returns

A table or a sequence of two tables

Details

Example 1

In a cyclic network with three vertices, each node can be reached in at most two steps.

>> N1 := Network::cycle([v1, v2, v3]):
   Network::allShortPath(N1)
                              table(
                                (v3, v3) = 0,
                                (v3, v2) = 2,
                                (v3, v1) = 1,
                                (v2, v3) = 1,
                                (v2, v2) = 0,
                                (v2, v1) = 2,
                                (v1, v3) = 2,
                                (v1, v2) = 1,
                                (v1, v1) = 0
                              )

Adding a vertex which has no connection to the three nodes, we get the expected entries infinity. The table of paths contains no entries referring to the newly added vertex.

>> N1 := Network::addVertex( N1, v4 ):
   Network::allShortPath(N1, Length, Path)
            table(
              (v4, v4) = 0,
              (v4, v3) = infinity,
              (v4, v2) = infinity,
              (v4, v1) = infinity,
              (v3, v4) = infinity,  table(
              (v3, v3) = 0,           (v3, v2) = [v3, v1, v2],
              (v3, v2) = 2,           (v3, v1) = [v3, v1],
              (v3, v1) = 1,       ,   (v2, v3) = [v2, v3],
              (v2, v4) = infinity,    (v2, v1) = [v2, v3, v1],
              (v2, v3) = 1,           (v1, v3) = [v1, v2, v3],
              (v2, v2) = 0,           (v1, v2) = [v1, v2]
              (v2, v1) = 2,         )
              (v1, v4) = infinity,
              (v1, v3) = 2,
              (v1, v2) = 1,
              (v1, v1) = 0
            )

Background

Changes




Do you have questions or comments?


Copyright © SciFace Software GmbH & Co. KG 2000