L3-Network Algorithms

L3 – Network Algorithms

NGEN06(TEK230) –
Algorithms in Geographical Information Systems

by: Irene Rangel, updated Nov. 2015 by Abdulghani Hasan,

Nov 2017 by Per-Ola Olsson
 L3-Network Algorithms

Content

1. General issues of networks

2. Shortest path - Dijkstra’s algorithm
3. Other shortest path algorithms
4. Neighbourhood graphs and clustering
5. Traveling salesman problem.
 L3-Network Algorithms

Networks in GIS
By using the distances between nodes in a
network we can e.g. derive the shortest path,
minimum number of nodes to pass and study
accessibility.
 L3-Network Algorithms

What is a network
• A network or graph has 2 main constitutes:
– Nodes
– Edges

Edges give distances between nodes. Distances can e.g. be:

- Euclidean distances
- Travelling time
The network can e.g. be:
- street network
- airplane routes
 L3-Network Algorithms

What is a network
• A network or graph has 2 main constitutes:
– Nodes
– Edges

Many analysis in networks only consider the nodes and

the edges.

Geometric location of the nodes is uninteresting

 L3-Network Algorithms

General issues of networks

Networks can be stored in matrixes.
Not a good data storage, especially for sparse
networks, since it requires a lot of memory.
But a matrix gives fast access to the nodes; O(1)
to access a single node. For example fast to
check if two nodes are connected.
In most cases relational databases or lists and
trees are more suitable storage structures.

A B C D

A 0 2 1 -
B 2 0 3 2
C 1 3 0 4
D - 2 4 0
”-” implies that the nodes are not connected by any edge
 L3-Network Algorithms

Graphic Adjacency matrix Adjacency list

Representation representation representation
(easy for humans
To read)

Source: Worboys and Duckham 2004

 L3-Network Algorithms

Sparse network with

several zeros stored

Graphic Adjacency matrix Adjacency list

representation representation representation

Source: Worboys and Duckham 2004

 L3-Network Algorithms

a connected to: b, distance 20 and

g, distance 15

Graphic Adjacency matrix Adjacency list

representation representation representation

Source: Worboys and Duckham 2004

 L3-Network Algorithms

Compare to matrix with one row

h connected to c,
distance 10

Graphic Adjacency matrix Adjacency list

representation representation representation

Source: Worboys and Duckham 2004

 L3-Network Algorithms

Shortest path

• The path between two nodes that is shorter than

all other possible paths.

• In the shortest path problem we are not only

restricted to Euclidean distances, but all the kind
of distances are of interest.
 L3-Network Algorithms

Shortest path

Navigation
Start point  target point
(distance c -> a is 28)

Accessibility
Many points target point
 L3-Network Algorithms

Shortest path

Navigation
Start point  target point

Accessibility
Many points target point
(access e from four points - c,d,f,g)
 L3-Network Algorithms

Shortest path

Accessibility to parks
and nature in Gothenburg
(Viktor Svanerud, master thesis)
 L3-Network Algorithms

Dijkstra’s algorithm
- one of the most well-known shortest path algorithms.

• Example of finding the shortest path between Node A

and Node D.
• We need 2 matrixes:
– Adjacency matrix (static)
– State matrix (dynamic)

A B C D

A 0 2 1 -
We recognise the
B 2 0 3 2 adjacency matrix from
C 1 3 0 4
D - 2 4 0
above
 L3-Network Algorithms

Dijkstra’s algorithm
• Example of finding the shortest path between Node A
and Node D.
• We need 2 matrixes:
– Adjacency matrix (static)
– State matrix (dynamic)
Node Distance Path Visited
A 0 - Yes
B 2 A No
C 1 A No
D  - No
Distance a -> b is 2

The state matrix is dynamic and changes when a node is “visited”.

 L3-Network Algorithms

Dijkstra’s algorithm
State matrix:
– Node is the ID of the nodes.
– Distance keeps track of the current shortest distance from the
starting node to this node.
– Path stores the previous node along the shortest path (found so
far) to this node.
– Visited states if the node has been visited in the computations of
the shortest path (explained later).

Node Distance Path Visited

A 0 - Yes

B 2 A No

C 1 A No

D  - No
Start point is A
 L3-Network Algorithms

Dijkstra’s algorithm
First initialize the state matrix:
– The start node is marked as visited.
– All nodes that can be reached from the start are updated in the columns distance
and path based on Adjacency matrix (row-wise).
• Distance values are set to the distances between the start node and the respective
node (derived from the adjacency matrix).
• Path values are set to the start node (the starting node is the current shortest path
to this particular node)
– If there is no path to a node, the distance is set to infinity and the path value is
undefined.

Node Distance Path Visited

A 0 - Yes

B 2 A No

C 1 A No

D  - No

The state matrix is initialized for start point A

 L3-Network Algorithms

Dijkstra’s algorithm
After the state matrix is initialized:

1. Find the node with the shortest distance that is not yet visited. Denote this as
the current node.

2. Mark the current node as visited.

3. For each node (m) that is not yet visited do:

If the node m and the current node has a common edge
AND
if the sum of the distance from the start node to the current node and the
distance from the current node to the node m (found in the adjacency
matrix) is shorter than the current distance from the starting node to node
m (stored in the state matrix)
DO State matrix
update the distance and the path for node m.

4. Proceed from (1) again until the end node is visited.

 L3-Network Algorithms

1. Find the node with the shortest distance that is not yet visited. Denote this as
the current node.

2. Mark the current node as visited.

3. For each node (m) that is not yet visited do:

If the node m and the current node has a common edge
AND
if the sum of the distance from the start node to the current node and the
distance from the current node to the node m (found in the adjacency
matrix) is shorter than the current distance from the starting node to node
m (stored in the state matrix)
DO
update the distance and the path for node m.

4. Proceed from (1) again until the end node is visited. Adjacency matrix
A B C D

Adjacency matrix: A 0 2 1 -
If nodes have a common edge and B 2 0 3 2
for distances between current node
and node m C 1 3 0 4

D - 2 4 0
 L3-Network Algorithms

Result of the shortest path algorithm

• Distance from start to end node (Distance)
• Path?

Node Distance Path Visited

A 0 - Yes

B 2 A Yes

C 1 A Yes

D 4 B Yes
 L3-Network Algorithms

Result of the shortest path algorithm

• Distance from start to end node (Distance)
• Path from end backwards to start.

Node Distance Path Visited

A 0 - Yes

B 2 A Yes

C 1 A Yes

D 4 B Yes
 L3-Network Algorithms

Does Dijkstra’s algorithm always give a

correct answer?
Yes, no heuristics are involved BUT all types of
distances are not allowed.

Conditions for a metric:

1. d(p,q)>=0, d(p,q)=0  p=q
2. d(p,q)=d(q,p) (symmetry)
3. d(p,q)<=d(p,r)+d(r,q) (triangle inequality)

Preparation for the network algorithm exercise.

 L3-Network Algorithms

What’s the computational complexity of

Dijkstra’s algorithm?
1. Find the node with the shortest distance and that is not yet visited.

2. Mark the current node as visited.

For each node (m) that is not yet visited do:

……………………………

4. Proceed from (1) again until the end node is visited.

 L3-Network Algorithms

Breadth-first traversal

Q is a queu – property is first-in-first-out

b is the
Source: Worboys and Duckham 2004
starting point

1. Start point b
2. Add nodes connected to b to Q and b to V
3. Add a (first in Q) to visited and add nodes connected to a LAST in Q.
4. Add c (first in Q) to visited and add nodes connected to c LAST in Q.
5. Add d (first in Q) to visited and add nodes connected to d LAST in Q.
6. ...
 L3-Network Algorithms

Breadth-first traversal

Q is a queu – property is first-in-first-out

b is the
Source: Worboys and Duckham 2004
starting point

1. Start point b
2. Add nodes connected to b to Q and b to V
3. Add a (first in Q) to visited and add nodes connected to a LAST in Q.
4. Add c (first in Q) to visited and add nodes connected to c LAST in Q.
5. Add d (first in Q) to visited and add nodes connected to d LAST in Q.
6. ...
 L3-Network Algorithms

Breadth-first traversal

Q is a queu – property is first-in-first-out

b is the
Source: Worboys and Duckham 2004
starting point

1. Start point b
2. Add nodes connected to b to Q and b to V
3. Add a (first in Q) to visited and add nodes connected to a LAST in Q.
4. Add c (first in Q) to visited and add nodes connected to c LAST in Q.
5. Add d (first in Q) to visited and add nodes connected to d LAST in Q.
6. ...
 L3-Network Algorithms

Breadth-first traversal

Q is a queu – property is first-in-first-out

b is the
Source: Worboys and Duckham 2004
starting point

1. Start point b
2. Add nodes connected to b to Q and b to V
3. Add a (first in Q) to visited and add nodes connected to a LAST in Q.
4. Add c (first in Q) to visited and add nodes connected to c LAST in Q.
5. Add d (first in Q) to visited. No “new” nodes connected to d.
6. ...
 L3-Network Algorithms

Breadth-first traversal

Q is a queu – property is first-in-first-out

b is the
Source: Worboys and Duckham 2004
starting point

3. …
4. Add c (first in Q) to visited and add nodes connected to c LAST in Q.
5. Add d (first in Q) to visited. No “new” nodes connected to d.
6. Add g (first in Q) to visited. No “new” nodes connected to g.
 L3-Network Algorithms

Breadth-first traversal

Q is a queu – property is first-in-first-out

b is the
Source: Worboys and Duckham 2004
starting point

3. …
4. Add c (first in Q) to visited and add nodes connected to c LAST in Q.
5. Add d (first in Q) to visited. No “new” nodes connected to d.
6. Add g (first in Q) to visited. No “new” nodes connected to g.
7. Add e (first in Q) to visited and add nodes connected to e LAST in Q.
8. …
 L3-Network Algorithms

Depth-first traversal

Q is a stack – property is last-in-first-out

b is the
Source: Worboys and Duckham 2004
starting point

1. Start point b
2. Add nodes connected to b to Q and add b to V
3. Add a (first in Q) to visited and add nodes connected to a FIRST in Q.
4. Add c (first in Q) to visited and add nodes connected to c FIRST in Q.
5. Add d (first in Q) to visited and add nodes connected to d FIRST in Q.
6. ...
 L3-Network Algorithms

Depth-first traversal

Now g is
added FIRST

Q is a stack – property is last-in-first-out

b is the
Source: Worboys and Duckham 2004
starting point

1. Start point b
2. Add nodes connected to b to Q and add b to V
3. Add a (first in Q) to visited and add nodes connected to a FIRST in Q.
4. Add c (first in Q) to visited and add nodes connected to c FIRST in Q.
5. Add d (first in Q) to visited and add nodes connected to d FIRST in Q.
6. ...
 L3-Network Algorithms

Depth-first traversal

Now we follow the

path a -> g “deeper”
and add e FIRST in Q

Q is a stack – property is last-in-first-out

b is the
Source: Worboys and Duckham 2004
starting point

1. Start point b
2. Add nodes connected to b to Q and add b to V
3. Add a (first in Q) to visited and add nodes connected to a FIRST in Q.
4. Add g (first in Q) to visited and add nodes connected to g FIRST in Q.
5. Add d (first in Q) to visited and add nodes connected to d FIRST in Q.
6. ...
 L3-Network Algorithms

Depth-first traversal

Q is a stack – property is last-in-first-out

b is the
Source: Worboys and Duckham 2004
starting point

1. Start point b
2. Add nodes connected to b to Q and add b to V
3. Add a (first in Q) to visited and add nodes connected to a FIRST in Q.
4. Add g (first in Q) to visited and add nodes connected to g FIRST in Q.
5. Add e (first in Q) to visited and add nodes connected to e FIRST in Q.
6. ...
 L3-Network Algorithms

Depth-first traversal

Q is a stack – property is last-in-first-out

b is the
Source: Worboys and Duckham 2004
starting point

1. Start point b
2. Add nodes connected to b to Q and add b to V
3. Add a (first in Q) to visited and add nodes connected to a FIRST in Q.
4. Add g (first in Q) to visited and add nodes connected to g FIRST in Q.
5. Add e (first in Q) to visited and add nodes connected to e FIRST in Q.
6. Add f (first in Q) to visited. No “new” nodes connected to f.
 L3-Network Algorithms

Depth-first traversal

Q is a stack – property is last-in-first-out

b is the
Source: Worboys and Duckham 2004
starting point

1. Start point b
2. Add nodes connected to b to Q and add b to V
3. Add a (first in Q) to visited and add nodes connected to a FIRST in Q.
4. Add g (first in Q) to visited and add nodes connected to g FIRST in Q.
5. Add e (first in Q) to visited and add nodes connected to e FIRST in Q.
6. Add f (first in Q) to visited. No “new” nodes connected to f.
7. Add c (first in Q) to visited and add nodes connected to c FIRST in Q.
 L3-Network Algorithms

Breadth-first, depth-first traversal

 L3-Network Algorithms

Dijkstra’s algorithm

Breadth-first or
Depth-first algorithm?
 L3-Network Algorithms

Dijkstra’s algorithm - breadth first algorithm

Dijkstra’s algorithm search in all

directions for the shortest path. It is an
breadth-first algorithm
 L3-Network Algorithms

Other shortest path algorithms

Algorithms with heuristics do not always give the best answer
(only a reasonably good answer is guaranteed).
Heuristic 1 – Direction limitation (nodes closer to the end node)
A* algorithm
Euclidean distances, depth-first & breadth-first

More likely that the shortest

path is “towards” the end node
 L3-Network Algorithms

Other shortest path algorithms

Algorithms with heuristics do not always give the best answer
(only a reasonably good answer is guaranteed).

Heuristic 2 – Hierarchical algorithm

Minor roads and major roads

Minor roads only the last and

first part of the route.
Major roads (highways) for the
main part of the route.
 L3-Network Algorithms

Other shortest path algorithms

Algorithms with heuristics do not always give the best answer
(only a reasonably good answer is guaranteed).

Heuristic 3 – super nodes (transit nodes)

Stored distances between

super nodes (transit nodes)
 L3-Network Algorithms

Neighbourhood graphs – minimum spanning tree (MST)

Minimum Spanning Tree (MST)

1. No isolated node
2.
 L3-Network Algorithms

Kruskal’s algorithm for computing MST

Edges
Original Ordered
Sort the edges in ascending
order after distance.

While there are isolated

nodes in the ordered list
add the currently
shortest node to the
MST.

Do NOT add nodes that

create a closed circle

Source: Sedgewick 2002

 L3-Network Algorithms

Neighbourhood graphs and Clustering

Visually easy to identify clusters,

but how to compute?
 L3-Network Algorithms

Neighbourhood graphs and Clustering

Minimum Spanning Tree

(MST)
1. No isolated node
2.
Threshold distance
 L3-Network Algorithms

Neighbourhood graphs and Clustering

Minimum Spanning Tree

(MST)
1. No isolated node
2.
Threshold distance
 L3-Network Algorithms

Traveling salesman problem (TSP)

1. Begin and end in the

same node (or in
different nodes)
2. Visit all nodes.
3. Minimize total length of
the route.
 L3-Network Algorithms

Traveling salesman problem (TSP)

How to solve the TSP problems?

To compute all possible combinations

and chose the shortest one is too
computational demanding.
It is NP-complete

Use the minimum spanning tree:

The maximum length of the TSP is at most 2 times the total
length of the MST
 L3-Network Algorithms

Traveling salesman problem (TSP)

How to solve the TSP problems?

Compute the MST e.g. with

Kruskal’s algorithm.

Do iterative improvements until no

further improvements are possible.

A local optimum of the TSP is found.