Shortest Path Problem

Question 1

Name typical examples for applications which deal with the shortest path problems

Answer 1

• Route planners
• Logistics systems
• Base data:
• Problem structure

Question 2

Differences of finding shortest walk and finding shortest path

Answer 2

Shortest Walk:
- can be undefined because arcs and nodes can appear repeatedly

Shortest Path:
- always well-defined

Question 3

Shortest Path tree characteristics

Answer 3

- In a shortest path tree, the unique path from s to node j
corresponds to the sought-after shortest path from s to j
- Node pred(j) is the predecessor node of node j in the corresponding
shortest path
- To determine all shortest paths from source s to all nodes of the
digraph, knowledge of the predecessor node pred(j) for j ∈ V \ {s}
is suffcient. The shortest path to node j results from "reading
backwards from destination to start" by means of the predecessor
function pred(·)
- Start sequences of shortest paths are shortest paths themselves

Question 4

Label setting algorithms (LSA)

Answer 4

• in each iteration (outer loop) the label of one node is fixed to its
  final value. This is achieved by means of the node selection rule
• potentially several labels are modified within one iteration of the
  outer loop
• prerequisites: acyclic graph or non-negative arc weights

Question 5

Label correcting algorithms (LCA)

Answer 5

• can modify all labels multiple times until the optimality conditions
  simultaneously hold for all arcs (i, j) ∈ A
• often use simpler selection rules compared to LSA → potentially
  better average-case performance, but usually inferior concerning
  worst-case performance
• LCA have no prerequisites concerning the weighted digraph
  (besides that no cycles of negative length are allowed)

Question 6

What does topological sorting mean?

Answer 6

A sorting (v1, v2, . . . , vm) of all nodes of digraph D is called
topological sorting if only arcs from a node with smaller index to a
node with larger index exist. Formally:
(vi, vj) ∈ A ⇒ i < j.

Question 7

Name the iterative procedure to generate topological sorting

Answer 7

1 remove randomly one of the nodes without predecessor
together with all incident arcs
2 repeat until no node can be removed anymore