10.6 Shortest-Path Problems

Question 1

Weighted Graphs :

length in these graphs:

Answer 1

Graphs that have a number assigned to each edge are called weighted graphs.

Length of a path in a weighted graph be the sum of the weights of the edges of this path.

Question 2

Theory of Dijkstra’s Algorithm.

Do the example to get the hang of it.

Answer 2

..

Question 3

ALGORITHM 1 Dijkstra’s Algorithm.

Answer 3

procedure Dijkstra(G: weighted connected simple graph, with
all weights positive)
{G has vertices a = v0, v1,… , vn = z and lengths w(vi, vj ) where w(vi, vj ) = ∞ if {vi , vj } is not an edge in G}
for i := 1 to n
L(vi) := ∞
L(a) := 0
S := ∅
{the labels are now initialized so that the label of a is 0 and all other labels are ∞, and S is the empty set}
while z ∉ S
u := a vertex not in S with L(u) minimal
S := S ∪ {u}
for all vertices v not in S
if L(u) + w(u, v) < L(v) then L(v) := L(u) + w(u, v)
{this adds a vertex to S with minimal label and
updates the labels of vertices not in S}
return L(z) {L(z) = length of a shortest path from a to z}

Question 4

show that this
algorithm always produces the length of a shortest path between two vertices in a weighted
graph:

Theorem 1:

Answer 4

Next, we use an inductive argument to show that Dijkstra’s algorithm produces the length
of a shortest path between two vertices a and z in an undirected connected weighted graph. Take
as the inductive hypothesis the following assertion: At the kth iteration
(i ) the label of every vertex v in S is the length of a shortest path from a to this vertex, and
(ii ) the label of every vertex not in S is the length of a shortest path from a to this vertex that
contains only (besides the vertex itself) vertices in S

THM:
Dijkstra’s algorithm finds the length of a shortest path between two vertices in a connected
simple undirected weighted graph.

Question 5

computational complexity of Dijkstra’s algorithm :

Answer 5

Dijkstra’s algorithm uses O(n2) operations (additions and comparisons) to find the length of
a shortest path between two vertices in a connected simple undirected weighted graph with n
vertices.

Question 6

Travelling Salesperson Problem:

Problem Statement:
and what it means.

Answer 6

The traveling salesperson problem asks for the circuit of minimum total weight in a weighted, complete, undirected
graph that visits each vertex exactly once and returns to its starting point.

This is equivalent to
asking for a Hamilton circuit with minimum total weight in the complete graph, because each
vertex is visited exactly once in the circuit

Question 7

Solution to TSP :

Answer 7

Need to examine (n − 1)!∕2 circuits to find ans.
So, use approximation algorithm.
That is, they may produce a Hamilton circuit with total weight W′ such that
W ≤ W′ ≤ cW, where W is the total length of an exact solution and c is a constant.
For example,
there is an algorithm with polynomial worst-case time complexity that works if the weighted
graph satisfies the triangle inequality such that c = 3∕2. For general weighted graphs for every
positive real number k no algorithm is known that will always produce a solution at most k times
a best solution. If such an algorithm existed, this would show that the class P would be the same
as the class NP