# Network Problems

## Concept of Network Problems

• Network problems are mathematical and logical problems that require the optimisation of routes through points known as vertices.
• The vertices are interconnected with paths known as edges or arcs, and the complete arrangement is called a graph or network.
• Directed graphs and undirected graphs are two types of graphs used in solving network problems. Directed graphs have edges with defined directions while undirected graphs don’t.

## Simplex Algorithm

• The simplex algorithm is a method to solve optimisation problems in linear programming.
• Designed by George Dantzig, it is an iterative method for obtaining the most optimal solution for a problem.
• An important concept in the simplex algorithm is the feasible region, which defines all the possible solutions to the problem.

## Types of Network Problems

• The different types of network problems include the shortest path problem, transportation problem, travelling salesman problem, minimum cost flow problem, and minimum spanning tree problem.

## Shortest Path Problem

• The shortest path problem involves finding the shortest possible route from one vertex to another within a graph.
• Dijkstra’s algorithm is a common approach used to solve this problem, where the path with the smallest total weight is identified.

## Travelling Salesman Problem

• The travelling salesman problem poses the challenge of finding the shortest possible route that covers all vertices and returns to the original vertex.
• This problem is known to be an NP-hard problem - a problem whose solution cannot be found in polynomial time.

## Minimum Cost Flow Problem

• The minimum cost flow problem aims to find the cheapest way to transport a certain amount of flow through a network from a source to a sink.
• Popular methods to solve this include the Simplex Algorithm and Network Simplex Algorithm.

## Practical Application and Exercises

• Real-life scenarios such as logistics planning or networking can aid in understanding the concept of network problems.
• Implementing the Simplex Algorithm or Dijkstra’s Algorithm in coding exercises can help reinforce understanding.
• Using contrasting examples to visualise different network problem types supports cognitive understanding.