5

Question 1

Shortest Path Problems in a Network Important Assumption

Answer 1

Shortest path problems are well de ned only if there is no circuit with a negative length. From now on, we will assume that this is always the case

Question 2

circuit

Answer 2

A circuit is a path whose endpoints are the same vertex
A chain (a cycle) is elementary if each vertex is present at most once
A chain (a cycle) is simple if each edge is present at most once

Question 3

chain

Answer 3

A chain in a graph is a sequence of vertices such that each pair of consecutive vertices in the sequence is connected by an edge. However, in a chain, vertices and edges can be repeated.

Question 4

path

Answer 4

A path in a graph is a special kind of chain where no vertices (and therefore no edges) are repeated. A path is a sequence of distinct vertices such that each consecutive pair of vertices in the sequence is connected by an edge.

Question 5

Bellman’s Principle of Optimality

Answer 5

In the context of shortest paths problems, this principle simply states
that a shortest path consists of shortest paths.
This doesn’t mean that the union of shortest paths is a shortest path !

Question 6

Dijkstra’s algorithm condition

Answer 6

a connected network R = (V, E, c), |V| = n, |E| = m, where c : E → R+
is a non-negative weighting of the arcs of the graph G = (V, E). A source s ∈ V