“This is the 28th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

One of the classic applications of graphs is the shortest path

Many problems in life can be solved by maps, such as the shortest path between two cities in the map, how to complete network wiring with the least cost, and the progress control in engineering.

Let’s take a look at some of the algorithms associated with obtaining shortest paths.

Dijkstra algorithm

  • The basic idea
  • Steps:
    • The data structure
      • G.edge [u][I] =

        weight; infinity: = ∞
        ,>
      • One-dimensional array dist[I] (record — shortest path length from origin U to node I)
      • One-dimensional array p[I] (record — precursor of node I on shortest path)
    • Initialize the
      • Set S = {u} + set
      • All nodes I in V minus S
      • dist[i] = G.Edge[u][i]
      • P [I] = u
      • Infinite p[I] = -1
    • To find the minimum
      • dist[t] = min
      • => Node T is the node closest to source point u in set V-S
    • Node T joins set S + updates set V-s
    • Determine whether to terminate (terminate when set V-S is null)
    • Take the easy way out
      • The neighbor j of node T can find the minimum path through node T
      • dist[j] > dist[t] + G.Edge[t][j] => dist[j] = dist[t] + G.Edge[t][j]
      • Record the precursor t of node J (p[j] = t)

Floyd algorithm

  • Alias: Interpolation method
  • Core: relaxation operation [Insert another node between two nodes to check whether the distance between two points can be shortened]
  • steps
    • The data structure
      • From node I to node J => edge: g.edge [I][j] = < I,j> weight; Infinity: = infinity
      • Auxiliary array
        • Dist [I][j] -> Record the shortest path length between two points
        • The precursor array p[I][j] -> records the precursor on the shortest path between two points
    • Initial (Dist [I][J] = G.edge [I][J])
      • There are edges p[I][j] = I
      • Infinite p[I][j] = -1
    • Insertion point
      • dist[i][j] > dist[i][k] + dist[k][j] => dist[i][j] = dist[i][k] + dist[k][j]
      • P [j] = P [k][J]

Bellman - Ford algorithm

  • steps
    • Data structure [edge set] (endpoint A + B + edge weight W)
    • Relaxation operation
    • Repeat the relaxation operation n-1 times
    • Negative loops (perform one more relaxation operation, if it can still be relaxed, there will be negative loops)

SPFA algorithm

  • Bellman-ford queue optimization algorithm
  • Monophyletic minimum path of solution with negative right edge | | to ring
  • Worst case: Time complexity as above O(nm)
  • High running efficiency of sparse graph O(km) (k << n)
  • steps
    • Create queue [source u is in queue + mark u is already in queue + number of times u is in queue (+1)]
    • Relaxation operation
      • Retrieve queue head X + mark X is not in the queue
      • Find all the exit edges of x I (x,v,w).
        • Dis [v] > dis [x] + [I] e w = > relaxation dis [v] = dis [x] + [I] e w
        • V is not in queue -> Check (number of queue entries + 1) >= n? (negative ring => exit operation) : (v join team + mark)
    • Repeat the previous step until the queue is empty

“

There are many usage scenarios of graphs, such as minimum spanning tree, topological sorting, etc. Those who are interested in graphs can continue to explore in depth