Article From:https://www.cnblogs.com/wangyuliang/p/9216365.html

 
       
 
During the summer vacation, Xiao hum is going to travel to some cities. Some cities have highways between them. In order to save money and facilitate the planned journey, Xiao Hun wants to know the shortest distance before any departure of any two cities before departure.
 
 
        In the above picture, there are 4 cities and 8 highways. The figures on the highway indicate the length of the highway. Please note that these roads are one-way. Now we need to find the shortest distance between any two cities, that is, to find the shortest path between any two points. This problem is also known as the “multi-source shortest path” problem.
 
        Now we need a data structure to store the information of the graph. We can still store it with a 4*4 matrix (two dimensional array E). For example, the distance between city 1 and city 2 is 2, and the value of e[1][2] is 2. No. 2 can not reach city 4, setting e[2][4] value.For infinity. Another place here is that a city itself is also 0 to oneself, for example, e[1][1] is 0, as follows.
        Now let’s go back to the question: how do we find the shortest path between any two points? Through previous studies, we know that through depth or breadth first search, we can find the shortest path between two points. Therefore, N2 depth search or breadth first search, that is, a depth or breadth first search for every two points, can be sought.The shortest path between any two points. But is there any other way?
 
        Let us think, according to our previous experience, if we have to shorten the distance between any two points (for example, from the vertex a point to the vertex b), only third points (vertex K) can only be introduced, and the vertex a point to the vertex can be shortened from the vertex K, that is, a-> k-> b.The journey of B. So what is the vertex of K in 1~n? Sometimes it’s not only through one point, but through two points or more points, the transfer is shorter, that is, a-> k1-> k2b-> or a-> k1-> K2… -&gT; k-> I… -> b. For example, the distance from city 4 to city 3 (4-> 3) is 12 in e[4][3]. If only transit through city 1 (4-> 1-> 3), the journey will be shortened to 11 (e[4][1]+e[1][3]=5+6=11). In fact, the city of No. 1 to No. 3 can also transit through the 2 City, reducing the distance from 1 to 3 to 5 (e[1][2]+e[2][3]=2+3=5). So if you pass through two cities in cities 1 and 2 at the same time,The distance from city 4 to city 3 will be further reduced to 10. Through this example, we find that each vertex can make the distance between the other two vertices shorter. OK, let’s generalge the problem.
 
        When third points are not allowed between any two points, the shortest distance between these cities is the initial distance.
       
 
 
If only 1 vertices are allowed now, how can we find the shortest distance between any two points? Just judge if e[i][1]+e[1][j] is smaller than e[i][j]. E[i][j] represents the distance from the vertex of I to the vertex of J. E[i][1]+e[1][j] represents the sum of the distances from vertex i to vertex 1, and from vertex 1 to vertex J. I is the 1~n loop, j is also the 1~n loop, and the code is implemented as follows.


1     for (i = 1; i <= n; i++)
2             {
3                 for (j = 1; j <= n; j++)
4                 {
5                     if (e[i][j] > e[i][1] + e[1][j])
6                         e[i][j] = e[i][1] + e[1][j];
7                 }
8             }

 

When only 1 vertices are allowed, the shortest distance between any two points is updated to:
 
        From the above picture, we found that the route of the 3 vertex to No. 2 vertex (e[3][2]), the vertex of No. 4 to the No. 2 vertex (e[4][2]), and the vertex of the 4 vertex to the 3 point (e[4][3]) have become shorter.
 
        Next, we continue to seek the shortest distance between any two points under the condition that only two vertices of 1 and 2 are allowed. How do you do it? We need to determine if the vertex of the No. 2 can make the I vertex to the vertex of the j vertex if the vertex of the number 2 passes through the shortest path that only allows any two points at the vertex of the number 1.The journey became shorter. That is to say, e[i][2]+e[2][j] is smaller than e[i][j], and the code is implemented as follows.
1 //Through the number 1 Vertex
2 for(i=1;i<=n;i++)  
3 for(j=1;j<=n;j++)  
4 if (e[i][j] > e[i][1]+e[1][j])  e[i][j]=e[i][1]+e[1][j];  
5 //Through the number 2 vertex
6 for(i=1;i<=n;i++)  
7 for(j=1;j<=n;j++)  
8 if (e[i][j] > e[i][2]+e[2][j])  e[i][j]=e[i][2]+e[2][j]; 
 
When only 1 and 2 vertices are allowed, the shortest distance between any two points is updated to:
        According to the above picture, it is allowed to transfer through the 1 and 2 vertices, making the e[1][3] and e[4][3] path shorter than only allowed through the vertex of No. 1.
 
        Similarly, the shortest path between any two points is continued in the case where only 1, 2 and 3 vertices are allowed to transit. The shortest path between any two points is updated as follows:
        Finally, all vertices are allowed to be transferred, and the shortest distance between any two points is:
        Although the whole algorithm is cumbersome, the code implementation is very simple. The core code is only five lines.
 

1     for(k=1;k<=n;k++)  
2     for(i=1;i<=n;i++)  
3     for(j=1;j<=n;j++)  
4     if(e[i][j]>e[i][k]+e[k][j])  
5                      e[i][j]=e[i][k]+e[k][j];  
 
The basic idea of this code is that at first, only 1 vertices are allowed to transit, and only 1 and 2 vertices are allowed to be transferred. All vertices of 1~n are allowed to be transferred to find the shortest distance between any two points. To sum up in one sentence, from the vertex of I to the vertex of J only.The shortest path of point K before crossing.
 1     #include 
 2     int main()  
 3     {  
 4     int e[10][10],k,i,j,n,m,t1,t2,t3;  
 5     int inf=99999999; //Use inf (infinity abbreviation) to store a positive infinity that we think. 6     //Read N and m, n indicates the number of vertices, and M represents the number of edges.
 7         scanf("%d %d",&n,&m);  
 8     //Initialization
 9     for(i=1;i<=n;i++)  
10     for(j=1;j<=n;j++)  
11     if(i==j) e[i][j]=0;    
12     else e[i][j]=inf;  
13     //Read the edge
14     for(i=1;i<=m;i++)  
15         {  
16             scanf("%d %d %d",&t1,&t2,&t3);  
17             e[t1][t2]=t3;  
18         }  
19     //Floyd-WarshallAlgorithm core statement
20     for(k=1;k<=n;k++)  
21     for(i=1;i<=n;i++)  
22     for(j=1;j<=n;j++)  
23     if(e[i][j]>e[i][k]+e[k][j] )   
24                         e[i][j]=e[i][k]+e[k][j];  
25     //The final result of the output
26     for(i=1;i<=n;i++)  
27         {  
28     for(j=1;j<=n;j++)  
29             {  
30                 printf("%10d",e[i][j]);  
31             }  
32             printf("\n");  
33         }  
34     return 0;  
35     }  
 
        It is also important to note that the Floyd-Warshall algorithm can not solve a graph with a “negative weight loop” (or a “negative weight loop”), since there is no shortest path with a “negative weight loop” graph. For example, there is no shortest path between vertex 1 and vertex 3 below. Because 1-&gT; 2-> 3-> 1-> 2-> 3->… -> 1-> 2-> 3, in such a way, the shortest path will decrease by 1 once every round 1-&gt, -2&gt, 3, and the shortest path will never be found. As a matter of fact,If there is a negative power loop in a graph, there is no shortest path in this graph.
 

Leave a Reply

Your email address will not be published. Required fields are marked *