Abstraction of shortest path problem
 In the network, find the path with the least sum of the weights of the edges among all paths between two different vertices
 This path is the shortest path between two points
 The first vertex is the source point
 The last vertex is the end point
Problem classification
 Single source shortest path problem: from a fixed source point, find the shortest path to all other vertices
 (directed) unauthorized map
 Power map
 Multi source shortest path problem: finding the shortest path between any two vertices
Single source shortest path algorithm for powerless graph
 Find the shortest path (BFS) to each vertex in ascending (non descending) Order
void Unweighted( Vertex S ) { Enqueue(S,Q); while(!IsEmpty(Q)) { V = Dequeue(Q); for( V Every adjacency point of W ) if( dist[W] == 1 ) { dist[W] = dist[V] + 1; path[W] = V; Enqueue(W,Q); } } }
 T = O(V+E)
A single source shortest path algorithm for weighted graphs

Negative circles are not considered

Find the shortest path to each vertex in ascending (non descending) Order

Dijkstra algorithm
 Let s = {source point s + determine the shortest path vertex v}
 For any vertex v not included, dist[v] is defined as the shortest path length from s to V, but the path only passes through the vertices in S. And the minimum length of path {s  > (VI ∈ s)  > V}
 If the paths are generated in increasing order, then
 The real shortest path must only pass through the vertex in S
 Choose the one with the smallest dist from the vertices never included (greedy)
 Increasing a v into S may affect the dist value of another w!
void Dijkstra( Vertex s ) { while(1) { V = Not included in vertex dist The youngest; if( In this way v Nonexistent ) break; collected[V] = true; for( V Every adjacency point of W ) if( collected[W] == false ) if( dist[V]+E<V,W> < dist[W] ){ dist[W] = dist[V]+E<V,W>; path[W] = V; } } }// Can't solve the problem with negative sides
 Method 1: scan all uninvolved vertices directly  O(V)
 T = O(V^2 + E) works well for dense maps
 Method 2: store dist in the minimum heap  O(logV)
 T = O(ElogV) is good for sparse image
Multi source shortest path algorithm
 Method 1: call the single source shortest path algorithm directly ðž“œ V
 T=O(âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£âˆ£
 Method 2: Floyd algorithm
 T=O(âˆ£ V âˆ£ 3) T=O(ã‚— V ã‚— 3) T=O(âˆ£ V âˆ£ 3) is good for dense map
 Floyd algorithm
void Floyd() { for( i=0; i<N; i++ ) for( j=0; j<N; j++ ) { D[i][j] = G[i][j]; path[i][j] = 1; } for( k=0; k<N; k++ ) for( i=0; i<N; i++ ) for( j=0; j<N; j++ ) if( D[i][k]+D[k][j] < D[i][j]) { D[i][j] = D[i][k]+D[k][j]; path[i][j] = k; } }

If there is a negative circle in the graph, can Floyd algorithm work? How to know if there is a negative circle in a graph?

You can use Floyd algorithm with simple transformation
Negative value can be regarded as a path that cannot be repeated infinitely
1) Check whether there is a negative value circle (check whether the weight has a negative value and find out the minimum negative value)
2) If there is a negative circle, increase the minimum negative value + 1 for the weight of all the non diagonal elements (for example, if the minimum negative value is  10, then the weight of all the non diagonal elements + 11), and the minimum negative value becomes 1
3) Using Floyd algorithm
4) Shortest path and length: directly output the shortest path saved in the matrix, and record the number of edges that the shortest path passes through n, the length is equal to the minimum negative value + 1 of the saved length minus the number of edges that the shortest path passes through
/* Single source shortest path algorithm of adjacency table store no right graph */ /* dist[]And path [] are all initialized to  1 */ void Unweighted ( LGraph Graph, int dist[], int path[], Vertex S ) { Queue Q; Vertex V; PtrToAdjVNode W; Q = CreateQueue( Graph>Nv ); /* Create an empty queue with MaxSize as an externally defined constant */ dist[S] = 0; /* Initialize source point */ AddQ (Q, S); while( !IsEmpty(Q) ){ V = DeleteQ(Q); for ( W=Graph>G[V].FirstEdge; W; W=W>Next ) /* For each adjacency point of V W  > adjv */ if ( dist[W>AdjV]==1 ) { /* If W  > adjv has not been visited */ dist[W>AdjV] = dist[V]+1; /* W>AdjV Distance update to S */ path[W>AdjV] = V; /* Record V on the path from S to W  > adjv */ AddQ(Q, W>AdjV); } } /* while End*/ }
/* A single source shortest path algorithm for storage weighted graph of adjacency matrix */ Vertex FindMinDist( MGraph Graph, int dist[], int collected[] ) { /* Return the smallest dist in the unrecorded vertices */ Vertex MinV, V; int MinDist = INFINITY; for (V=0; V<Graph>Nv; V++) { if ( collected[V]==false && dist[V]<MinDist) { /* If V is not included and dist[V] is smaller */ MinDist = dist[V]; /* Update minimum distance */ MinV = V; /* Update corresponding vertex */ } } if (MinDist < INFINITY) /* If the minimum dist is found */ return MinV; /* Return the corresponding vertex subscript */ else return ERROR; /* If such a vertex does not exist, an error mark is returned */ } bool Dijkstra( MGraph Graph, int dist[], int path[], Vertex S ) { int collected[MaxVertexNum]; Vertex V, W; /* Initialization: the edge that does not exist in the default adjacency matrix is represented by INFINITY */ for ( V=0; V<Graph>Nv; V++ ) { dist[V] = Graph>G[S][V]; if ( dist[V]<INFINITY ) path[V] = S; else path[V] = 1; collected[V] = false; } /* First, set the starting revenue */ dist[S] = 0; collected[S] = true; while (1) { /* V = The smallest dist in the unrecorded vertices */ V = FindMinDist( Graph, dist, collected ); if ( V==ERROR ) /* If such a V does not exist */ break; /* Algorithm termination */ collected[V] = true; /* V included */ for( W=0; W<Graph>Nv; W++ ) /* For each vertex W in the graph */ /* If W is the adjacency of V and is not included */ if ( collected[W]==false && Graph>G[V][W]<INFINITY ) { if ( Graph>G[V][W]<0 ) /* If there are negative edges */ return false; /* Unable to resolve correctly, error flag returned */ /* If V makes dist[W] smaller */ if ( dist[V]+Graph>G[V][W] < dist[W] ) { dist[W] = dist[V]+Graph>G[V][W]; /* Update dist[W] */ path[W] = V; /* Update S to W path */ } } } /* while End*/ return true; /* The algorithm is completed, and the correct mark is returned */ }
/* Memory multisource shortest path algorithm of adjacency matrix */ bool Floyd( MGraph Graph, WeightType D[][MaxVertexNum], Vertex path[][MaxVertexNum] ) { Vertex i, j, k; /* Initialization */ for ( i=0; i<Graph>Nv; i++ ) for( j=0; j<Graph>Nv; j++ ) { D[i][j] = Graph>G[i][j]; path[i][j] = 1; } for( k=0; k<Graph>Nv; k++ ) for( i=0; i<Graph>Nv; i++ ) for( j=0; j<Graph>Nv; j++ ) if( D[i][k] + D[k][j] < D[i][j] ) { D[i][j] = D[i][k] + D[k][j]; if ( i==j && D[i][j]<0 ) /* If a negative circle is found */ return false; /* Unable to resolve correctly, error flag returned */ path[i][j] = k; } return true; /* The algorithm is completed, and the correct mark is returned */ }