Unit 5 - Shortest Path Problem

Question 1

Diagraph or Directed graph

Answer 1

Is a graph in which the edges have a direction.
The pair of nodes (i,j) is always an ordered pair, starting node i and ending node j.

Question 2

In-degree

Answer 2

Indicates how many directed edges leads to this node.

Question 3

Out-degree

Answer 3

Indicates how many directed edges leads away from this node.

Question 4

How to calculate the degree of a node in a diagraph?

Answer 4

The degree of a node in a diagraph is the sum of the input and output nodes.

Question 5

The adiacent matrix of a diagraph is symmetric?

Answer 5

Generally no, because an arrow connects a node to another in only one direction.

Question 6

Weighted graph

Answer 6

It’s a graph where there’s a mapping that assigns to every edge a weight.

Question 7

Unweighted graph

Answer 7

A graph without a weight function.

Question 8

How to assign a weight?

Answer 8

Wij = w({ Vi,Vj })

Question 9

What’s the weight of the elements on the main diagonal of a weighted graph?

Answer 9

0, it cost nothing to stay in one node.

Question 10

Dijkstra’s algorithm

Answer 10

Determines the shortest path from a starting node to all other nodes in a weighted simple graph with non-negative weights.

Question 11

Dijkstra’s algorithm steps

Answer 11

The algorithm iteratively goes to the successor node with the shortest path known so far and tests wether a shorter path to one of the neighboring nodes can be found via this node.