Summary

In this lesson network analysis was discussed. Network analysis is primarily concerned with the relationships between objects. To investigate these (distance) relationships, we need knowledge about the existing primitives (see 1.1.1 Primitives of a Network) and measurements. This is possible with the help of a description about the structure of networks (see 1.2 Structural Properties of a Network).

The computation of shortest paths is a common application of network analysis and graph theory. In this context, the Dijkstra algorithm which is the most commonly used algorithm for computing shortest paths in edge-weighted graphs, has been presented. The pseudocode of the algorithm was presented and explained by means of a step-by-step animation of the algorithm. It was also stressed that for special applications and special types of graphs (weighting of nodes, negative edge weights) modifications or alternative algorithms are required to calculate distance.

Furthermore, the Travelling Salesman Problem (TSP) was presented which dealt with the question of how route calculation for several stops can be optimized for minimal distance travelled. In this context, the vehicle routing problem was introduced. It extends the TSP to the effect that minimizing transportation cost and the number of vehicles used was also considered. Exact and heuristic algorithms and also interactive and combined solution methods provide solutions to such problems. It was shown that heuristic approaches are preferred when using large data dets since exact algorithms are computationally complex.