2. The most common problem solved by weighted graph is the shortest path problem (pps).
3. There are all vertices and necessary edges connecting them in the minimum spanning tree of the weighted graph, and the weights of these edges are the smallest.
4. The priority queue algorithm can be used to find the minimum spanning tree of the weighting graph.
5. Solving method of minimum spanning tree of undirected weighted graph.
1) Find all edges from the latest vertex to other vertices, which cannot be in the set of trees, and use these edges as the priority queue.
2) Find the edge with the least weight and put it and the vertex it reaches into the set of trees.
3) Repeat the above steps until all vertices are in the set of trees.
6. The shortest path problem of weighted graph can be solved by Dijkstra algorithm. The algorithm is based on the adjacency matrix representation of graphs. It can not only find the shortest path between any two points, but also find the shortest path from a specified point to all other vertices.
The idea of Dijkstra algorithm;
Take finding a route with the lowest cost from one city to another as an example (assuming that the cost of all routes cannot be directly derived, only the cost to neighboring cities can be directly known).
1) Send an agent to a new city at a time, use the new information provided by this agent to modify and improve the expense list, and keep the lowest cost from the source point to a city in the list.
2) Constantly sending agents to a new city, provided that the route cost from the source point to that city is the lowest.
draw
7. Sometimes in order to see whether a route is feasible, it is necessary to create a connection table. In weighted graphs, tables are used to give the minimum cost between any two vertices, which may be connected by several edges. This problem is called the shortest path problem between each pair of vertices. Warshall algorithm (which is described in detail in the stamp) can quickly create such a connection table. A similar method in weighted graph is called Freudian algorithm.
The difference between Floyd algorithm and Warshall algorithm. When a two-segment path is found in the Warshall algorithm, it is simply to insert 1 into the table. In Floyd algorithm, it is necessary to add the weights of both ends and insert their sum.