Data structure Interview # 9 — Common operations on graphs # 2 Shortest paths

Note: There are related exercises in the interview book, but the idea is relatively unclear, and there are typesetting mistakes. The author has rewritten the relevant books and his own views for your reference.

Common operations of graph 2 shortest path

(I) The steps of the core thought of the shortest path are as follows:

(1) Starting from the selected source vertex, select the vertex X connected to the source vertex with the lowest weight and has not been identified, mark X as True and record the path length;

(2) Then compare whether the sum of the paths connecting the vertex X and the other vertices is less than the direct path length from the source vertex to the other vertices, if yes, modify the path length; If no, it will remain unchanged;

(3) Loop through (1) until all vertices are identified as True.

For easy comprehension, the steps are illustrated in the following tables. The initial graph structure is shown as follows: the value in the table is the weight between Vertex4,Vertex1, for example, (Vertex4,Vertex1) =10 means that the path weight between Vertex4 and Vertex1 is 10.

Suppose we find the shortest path length from vertex 0 to the remaining vertices.

Prerequisite: initial operation, store weights from 0 to each vertex in array weights[][]; Store the minimum weight discovery identifier into the array weightFound[] and initialize weightFound[0]=true(because 0 is the source point).

Step 1: find and select the vertex with minimum weight from vertex 0 to other vertices, and the search point is not identified by true. Obviously, Vertex3 is chosen here.

The execution steps of the algorithm are shown in the figure below:

Step 2: Find and select the vertex from vertex 0 to the minimum weight value of the remaining vertices, and this point has not been identified with true.

Obviously, Vertex 4 is selected here.

The execution steps of the algorithm are shown in the figure below:

Step 3: Find and select the vertex from vertex 0 to the minimum weight value of the remaining vertices, and this point has not been identified with true.

Obviously, Vertex 2 is selected here.

The execution steps of the algorithm are shown in the figure below:

Step 4: Find and select the vertex from vertex 0 to the minimum weight value of the remaining vertices, and this point has not been identified with true.

Obviously, Vertex 1 is selected here.

The execution steps of the algorithm are shown in the figure below:

At this point, all flags are True, and the comparison ends. The shortest paths from vertex 0 to other points are as follows:

//inifinity stands for infinity, that is, unreachable.
int g_WeightMatrix[5] [5] ={infinity,16,infinity,2.3,
       infinity,infinity,5,infinity,infinity,
       infinity,3,infinity,infinity,infinity,
       infinity,12,infinity,infinity,7,
       infinity,10.4.5,infinity};
 
template <class vType.int size>
class weightedGraphType : publicgraphType<vType, size>
{
public:
       voidcreateWeightedGraph(a);voidshortestPath(vType vertex);
       voidprintShortestDistance(vType vertex);
protected:
       intweights[size][size];  // Weight matrix
       intsmallestWeight[size]; // Shortest path from source to other vertices
};
Copy the code

\

1. Create a weight diagram

When we created the weight diagram, we simplified it. I’m just assigning the given array of weights. [With a little modification here, you can manually enter the relationship between vertices and adjacent edges]. The storage structure of graph is adjacency matrix.

template <class vType.int size>
voidweightedGraphType<vType,size>::createWeightedGraph()
{
       gSize= size;
       for(int i = 0; i < size; i++)
       {
              smallestWeight[i]= 0;
              for(int j =0; j < size; j++)
              {
                     weights[i][j]= g_WeightMatrix[i][j];
                     cout<< weights[i][j] << "\t"; } cout<< endl; }}Copy the code

2. Find the shortest path (1 source node to other nodes Dijkstra algorithm)

template <class vType.int size>
voidweightedGraphType<vType,size>::shortestPath(vType vertex)
{
       intv=0;
       intminWeight;
      
// Initialize 0 to self,infinity to unreachable.
// The weights from vertex to j are recorded in the array
       for(intj = 0; j < gSize; j++)
       {
              smallestWeight[j]= weights[vertex][j];
       }
       boolweightFound[size];
       // Whether the weight applies the identifier...
       for(intj = 0; j < gSize; j++)
       {
              weightFound[j]= false;             
       }
 
       weightFound[vertex]= true;   // Initial Settings
       smallestWeight[vertex]= 0;   // The minimum weight is 0 or infinity.
 
// Closing tag -- loop once (i.e., all points have been identified).
// The number of cycles is gsize-2 because vertex nodes are already identified as true.
       for(int i = 0; i < gSize- 1; i++)
       {
              minWeight= infinity;   
// Find the least weighted unlabeled vertex from all vertices,
//v records the vertex,minWeight records the weight value.
              for(int j = 0; j < gSize; j++)
              {
                     if(! weightFound[j]) {if(smallestWeight[j]< minWeight)
                            {
                                   v= j;
                                   minWeight= smallestWeight[v];
                            }//endif
                     }//endif
              }//endfor j
              // point v is used.
              weightFound[v]= true;
      
+ (v-> destination) + (v-> destination)
// Whether the weight value is < recorded smallestWeight. If it is small, replace it. Otherwise, no change.
              for(int j = 0; j < gSize; j++)
              {
                     if(! weightFound[j]) {if(minWeight+ weights[v][j] < smallestWeight[j]) { smallestWeight[j]= minWeight + weights[v][j]; }}}//endfor j (in)
       }//endfor
}
Copy the code

3. Print the shortest path

// Print the shortest path source from vertex to other nodes…

template <class vType.int size>
voidweightedGraphType<vType,size>::printShortestDistance(vType vertex)
{
       cout<< "Source vertex: " << vertex << endl;
       cout<< "Shorest distance from source to each vertex" << endl;
       cout<< "Vertex Shortest_Distance" << endl;
 
       shortestPath(vertex);
       for(int j = 0; j < gSize; j++)
       {
              cout<< setw(4) << j << setw(12) << smallestWeight[j]<< endl;
       }
       cout<< endl;
}
Copy the code

\