A container truck driver was ordered to transport a load of goods from place A to place B in the shortest time. The road network from A to B is criss-crossed, so there are many driving routes. Which route should the driver choose? Assuming that the running speed of container trucks is constant, this problem is equivalent to finding the shortest path from A to B.

2 highway connection problem

There are several big cities in a certain area, and now it is ready to build expressways to connect these cities, so that any one of them can reach another city directly or indirectly through expressways. Assuming that the cost of building an expressway between any two cities is known, how should we decide which cities to build an expressway between to minimize the total cost?

3 assignment problem (assignment problem)

The manager of a company is going to arrange 20 employees to complete 20 tasks, one for each. Because of the different characteristics of employees, different employees get different returns when they complete the same task. How to allocate the work plan to maximize the total return?

4 Chinese postman problem (CPP- Chinese postman problem)

The postman is responsible for delivering mail in a certain block. How to design a shortest delivery route for him or her (starting from the post office, passing through every street in the delivery area at least once and finally returning to the post office)? Because this problem was first put forward by Professor Guan Meigu of China in 1960, it is called the Chinese postman problem internationally.

5 Traveling Salesman Problem (TSP- Traveling Salesman Problem)

A salesman is going to several cities to promote his products. How to design a shortest travel route for him or her (starting from the resident, passing through each city just once and finally returning to the resident)? The research history of this problem is very long, and it is usually called the traveling salesman problem.

6 transportation problem (transportation problem)

Some raw materials are of origin, and now they need to be transported from the origin to the factories that use them. Assuming that the output of one place of origin and the demand of two factories are known, and the freight of unit product from any place of origin to any factory is known, how to arrange the transportation scheme to minimize the total transportation cost?

7. The shortest path has a mature algorithm: Dijkstra algorithm.

8. To calculate the shortest path between each pair of vertices in the weighted graph, Dijkstra algorithm can obviously be called. The specific method is to use Dijkstra algorithm to find the shortest path from this starting point to the rest of the vertices, and repeat this operation for n times to get the shortest path from each vertex to other vertices. The time complexity of this algorithm is O (n 3). The second method to solve this problem is an algorithm proposed by Floyd R W, which is called Floyd algorithm. (Can solve the first problem)

9.prim algorithm and Kruskal algorithm construct the minimum spanning tree (connecting all points).

10. Hungarian algorithm and Kuhn-Munks algorithm solve the personnel allocation problem.

Fleury algorithm of 1 1 Eulerian path (postman problem in China)

12. An algorithm of maximum flow-labeling method) The basic idea of labeling method to find the maximum flow of network is to find the augmented orbit, so that the network traffic will increase continuously until it reaches the maximum. )

My computer is not good, I use MATLAB, and Baidu can find a lot of information online. The program is too direct, and Baidu's corresponding algorithms are all made into C. ...

Baidu can achieve many algorithms. ...