1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
shortest(1) -- Compute the distance between one node and all the other nodes of a graph
======
## SYNOPSIS
`shortest` <graph_in> <node> [SHOW]
## DESCRIPTION
`shortest` computes the distance (and the shortest paths) between a
given node and all the other nodes of an undirected graph provided as
input. The program implements the Breadth-First Search algorithm.
## PARAMETERS
* <graph_in>:
input graph (edge list) if equal to `-` (dash), read the edge list
from STDIN.
* <node>:
The label of the node from which distances are to be computed
* SHOW:
If the third (optional) parameter is equal to `SHOW`, the program
will dump on the standard error also all the shortest paths
between <node> and all the other nodes of the graph
## OUTPUT
`shortest` prints on the standard output the distances betwen <node>
and all the other nodes of the graph, in the format:
d0 d1 d2 d3.....
where `d0` is the distance to node `0`, `d1` is the distance to node
`1`, and so forth. If `SHOW` is given, the list of all the shortest
paths between <node> and the other nodes is printed on the standard
error, one path per line, in the format:
label0 label1 label2 ... node
where `label1`, `label2`, etc. are the labels of a shortest path
between `label0` and <node>
## EXAMPLES
The following command:
$ shortest er_1000_5000.net 25
3 4 4 4 2.......
$
will show on output the distances between node 25 and all the other
nodes in the graph `er_1000_5000.net`. If we invoke the program with:
$ shortest er_1000_5000.net 25 SHOW 2>er_1000_5000.net_25_paths
3 4 4 4 2.......
$
the program will dump on STDERR the list of all the shortest paths
between 'node' and all the other nodes of the graph. Since we used the
redirection `2>er_1000_5000.net_25_paths` (which can be read "redirect
STDERR to 'er\_1000\_5000.net\_25\_paths' "), the list of shortest
paths will be written to the file `er_1000_5000.net_25_paths`.
## SEE ALSO
dijkstra(1), bet_dependency(1), betweenness(1), shortest_avg_max_hist(1)
## REFERENCES
* V\. Latora, V. Nicosia, G. Russo, "Complex Networks: Principles,
Methods and Applications", Chapter 3, Cambridge University Press
(2017)
* V\. Latora, V. Nicosia, G. Russo, "Complex Networks: Principles,
Methods and Applications", Appendix 6, Cambridge University Press
(2017)
## AUTHORS
(c) Vincenzo 'KatolaZ' Nicosia 2009-2017 `<v.nicosia@qmul.ac.uk>`.
|
