This is the 13th day of my participation in the August More Text Challenge. For details, see:August is more challenging

The shortest path

  • Typical use: Traffic problems. For example: there are several routes from city A to city B, but the transportation cost (or time required) of each route is different, so how to choose A route to minimize the total cost (or total time)?
  • Abstract: Among the multiple paths from point A (source point) to point B (end point) in the weighted directed graph, find A path with the minimum sum of weights of each edge, that is, the shortest path.

Unlike the minimum spanning tree, the shortest path does not necessarily contain n vertices

Two common shortest path problems

Dijkstra algorithm — single source shortest path

Algorithm thought

Divide the set of vertices in the graph into two groups:

The first group is the vertex set S whose shortest path has been found and the second group is the vertex set U whose shortest path has not been determined

  1. Initially, S contains only the source point, S={v}, and U contains all vertices except v;
  2. Take a vertex k with the smallest distance from U and add k to S;
  3. Take k as the new intermediate point, modify the distance of each vertex in U;
  4. Repeat steps 2 and 3 until all vertices are contained in S

Algorithm implementation

Algorithm flow chart C++ code implementation

void ShortestPath_DIJ(AMGraph G, int v0){
	// Use Dijkstra algorithm to find the shortest path from vertex V0 to other vertices of directed network G
	n = G.vexnum;  // Number of vertices in G
	for(v = 0; v < n; v++){
		// N vertices are initialized in sequence
		S[v] = false;  // S starts with an empty set
		D[v] = G.arcs[v0][v];  // Initialize the shortest path length from v0 to each endpoint
		if(D[v] < MaxInt) Path[v] = v0;  // There is an arc between v0 and v, set the precursor of V to v0
		else Path[v] = - 1;  // If there is no arc between v0 and v, set the precursor of V to -1
	}
	S[v0] = true;  // Add v0 to S
	D[v0] = 0;  // The distance from the source point is 0

	/* -- Start the main loop, each time finding the shortest path from v0 to some vertex V, adding v to set S -- */
	for(i = 1; i < n; i++){
		// Calculate the remaining n-1 vertices in sequence
		min = MaxInt;
		for(w = 0; w < n; w++)
			if(! S[w] && (D[w] < min)){ v = w; min = D[w];// Select a current shortest path with endpoint v
			}
		S[v] = true;  // Add v to S
		for(w = 0; w < n; w++)  // Update the shortest path length from v0 to all vertices in set V−S
			if(! S[w] && ((D[v] + G.arcs[v][w]) < D[w])){ D[w] = D[v] + G.arcs[v][w];/ / update D [w]
				Path[w] = v;  // Update w precursor to V}}}Copy the code

Floyd’s algorithm — the shortest path between all vertices

The shortest path between each pair of vertices

Method 1: each time with a vertex as the source point, repeat Dijkstra algorithm n times — T(n)=O(n³) Method 2: Floyd (Floyd) algorithm idea: vertex by vertex heuristic method

Algorithm thought

  • Set a square matrix of order n initially, let its diagonal element be 0, if there is arc

    , then the corresponding element is the weight; It is up
    ,vj>
  • Step by step, try to add intermediate vertices to the original direct path. If the path becomes shorter after adding intermediate points, modify it. Otherwise, maintain the original value.
  • When all vertices are probed, the algorithm ends

Algorithm implementation

typedef int Pathmatirx[MAXVEX][MAXVEX]
typedef int ShortPathTable[MAXVEX][MAXVEX]

/* -Floyd algorithm to find the shortest path P[v][w] and weighted length D[v][w] -*/ from each vertex V to the rest vertices W in the network graph G
void ShrotestPath_Floyd(MGraph G, Pathmatirx* P, ShortPathTable* D){
	int v, w, k;
	for(v = 0; v < G.numVertexes; ++v){
		// Initialize D and P
		for(w = 0; w < G.numVertexes; ++w){
			(*D)[v][w] = G.matirx[v][w];  // the value of D[v][w] is the weight between the corresponding points
			(*P)[v][w] = w;  // Initialize P}}for(k = 0; k < G.numVertexes; ++k)
		for(v = 0; v < G.numVertexes; ++v)
			for(w = 0; w < G.numVertexes; ++w)
				if((*D)[v][w] > (*D)[v][k] + (*D)[k][w]){
					// If the vertex path is shorter than the original path between two points
					// Set the weight between the current two points to a smaller one
					(*D)[v][w] = (*D)[v][k] + (*D)[k][w];
					(*P)[v][w] = (*P)[v][k];  // Set the path to go through vertices with index K}}Copy the code