This is the 25th day of my participation in the August Genwen Challenge.More challenges in August

The application of figure

Shortest path

For a weighted graph, the sum of weights on the edges of a path (possibly more than one) from one vertex ๐‘ฃ0 to any other vertex ๐‘ฃ๐‘– is defined as the weighted path length of the path, and the path with the shortest length of the weighted path is called the shortest path

Algorithms for solving shortest paths usually rely on the property that the shortest path between two points also includes the shortest path between other vertices along the path

1.๐‘ซ๐’Š๐’‹๐’Œ๐’”๐’•๐’“๐’‚ algorithm to solve the single source shortest path problem

In addition, there are two auxiliary arrays dist[]: record the current shortest path length from the source point ๐‘ฃ0 to other vertices. Initially dist[I]=arcs[๐‘ฃ0][I], Arcs [๐‘ฃ0][I] is the initial value of the adjacency matrix path[]: Path [I] represents the precursor node of the shortest path from the source point to vertex I. After the algorithm is completed, the shortest path adjacency matrix arcs from the source point ๐‘ฃ0 to vertex ๐‘ฃ๐‘– can be traced according to its value. [] Arcs [I][j] represents the weight of directed edge < I,j>, if it does not exist in edge < I,j> then arcs[I][j]=โˆž. The steps of Dijkstra’s algorithm are as follows: Algorithms for solving the shortest path usually rely on one property: the shortest path between two points also contains the shortest path between other vertices on the path

Dijkstra algorithm steps are as follows:

(1) the initialization: set S initialization {0}, dist [] initial value dist [I] = arcs [0] [I], I = 1, 2, 3,… ,n-1

(2) from the selected vertices V – S V ๐‘—, meet dist [j] = Min {dist [I] ๐‘– | V โˆˆ ๐‘‰ – ๐‘†}, V ๐‘— is a current obtained from where v0 of the end of the shortest path to S = S โˆช {j}

Dist [k]= dist[j]+arcs[j][k]<dist[k]; dist[j]+arcs[k]= dist[j]+arcs[k]

โ‘ฃ Repeat โ‘กโ‘ข a total of N-1 times until all vertices are contained in S

Note:

, if only from a source to a particular point of the shortest path still need to run the Dijkstra algorithm, the time complexity is O (| ๐‘‰ | 2), if you want to find out all the nodes of the shortest path between, the time complexity is O (| ๐‘‰ | 3), the Dijkstra algorithm is not suitable for figure with negative weights

2.Floyd algorithm to solve the shortest path problem between vertices

Note:

  • Floyd algorithm time complexity is O (| ๐‘‰ | 3), although compared with the Dijkstra algorithm without an order of magnitude level of efficiency, but its compact code, and thought simple, so widely used
  • Floyd’s algorithm allows a graph to have negative-weighted edges, but does not allow it to contain loops of negative-weighted edges
  • Floyd algorithm is also suitable for weighted undirected graphs, which can be regarded as directed graphs with double round-trip edges

3. Topology sorting

Directed acyclic graph: a directed graph with no rings is called a directed acyclic graph, or DAG graph for short

AOV network: If a DAG graph is used to represent a project, its vertices represent activities, and directed edges <๐‘‰๐‘–,๐‘‰๐‘—> indicate that activities ๐‘‰๐‘– must precede activities ๐‘‰๐‘—, such a directed graph is called a network of vertices represent activities and is denoted as AOV network

1. A sort of vertices of directed acyclic graphs as follows:

โ‘  Each vertex appears only once

โ‘ก If vertex A is ahead of vertex B in the sequence, there is no path topological sorting algorithm from vertex B to vertex A in the graph: โ‘  Select A vertex without A precursor (entry degree is 0) from the DAG graph and output it

โ‘ก Remove the vertex and all directed edges starting from the graph

โ‘ข Repeat until the DAG graph is empty or there are no vertices without a precursor in the current graph, which actually indicates that the directed graph has a loop

Note: Any DAG diagram has one or more topological ordering sequences, and topological ordering is not unique

Topological sorting algorithm implementation

bool  TopologicalSort(Graph G){
InitStack(S);                                           // Initializes the stack to store vertices with degree 0
for(int  i=0; i<G.vexnum; i++)if(indegree[i]==0)
Push(S,i);                                  // Stack all vertices with an entry degree of 0
int  count=0;                                          // Record the number of vertices output while(! IsEmpty(S)){
Pop(S,i);
print[count++]=i;                          // for(p= g.vertices [I]. Firstarc; p! =NULL; p=p->nextarc){
v=p->adjvex;                         // Decrement the input of all vertices to which I points by 1 and set the input to if(! (--indegree[v])) // The vertex decrement to 0 is pushed into SPush(S,v); }}if(count<G.vexnum)
return  false;                            // Sort failed, there is a loop in the digraph
else return true; // Topology sort succeeded
}

Copy the code

Note:

  • Topological sort to the output of each vertex at the same time deleted at the edge of it as a starting point, so the topological sort time complexity is O (+ | | V | E |)
  • The result of a topological sort is usually not unique, but is unique if the vertices are already in a linearly ordered sequence (such as an adjacency list)
  • Because all vertices in DAG graph have equal status and the number of vertices is artificially chosen, if the vertices are rearranged according to the result of topological sorting, the new adjacency matrix of DAG graph generated must be triangular matrix
  • Conversely, if the adjacency matrix of a directed graph is a triangular matrix, there must be topological sequence