SPFA algorithm usage tutorial

Scope of application: There are negative weight edges in a given graph. At this time, algorithms such as Dijkstra have no place to use, and the complexity of the Bellman-Ford algorithm is too high, so the SPFA algorithm comes in handy. . We agree that there is no negative weight cycle in the directed weighted graph G, that is, the shortest path must exist. Of course, we can do a topological sort before executing the algorithm to determine whether there is a negative weight cycle, but this is not the focus of our discussion.

Algorithm idea: We use array d to record the shortest path estimate of each node, and use an adjacency list to store graph G. The method we adopt is the dynamic approximation method: set up a first-in-first-out queue to save the nodes to be optimized. During optimization, we take out the head node u each time, and use the current shortest path estimate of point u to leave point u. The node v pointed to undergoes a relaxation operation. If the shortest path estimate of point v is adjusted and point v is not in the current queue, point v is placed at the end of the queue. In this way, nodes are continuously taken out from the queue to perform relaxation operations until the queue is empty

The expected time complexity is O(ke) , where k is the average number of times all vertices enter the team. It can be proved that k is generally less than or equal to 2.

Implementation method:

Create a queue. Initially, there is only the starting point in the queue. , and then create a table to record the shortest path from the starting point to all points (the initial value of the table should be assigned to the maximum value, and the path from the point to itself should be assigned to 0). Then perform a relaxation operation, using some points in the queue as the starting point to refresh the shortest path to all points. If the refresh is successful and the refreshed point is not in the queue, the point is added to the end of the queue. Repeat until the queue is empty.

Determine whether there is a negative loop:
If a point enters the queue more than N times, there is a negative loop (SPFA cannot handle negative loops picture)

First establish the shortest
from the starting point a to the other points Path table

       #　1. The first element (a) of the team is dequeued, and the relaxation operation is performed on the end points of all edges with a as the starting point (there are three points b, c, and d here). At this time, the path table status is:

         Point
needs to be added to the queue. At this time, three new nodes b, c, and d are added to the queue.

The first element of the team, point b, is dequeued. Relax the end points of all edges with b as the starting point in sequence (there is only point e here). At this time, the path table status is:

                          

#In the shortest path table, the shortest path estimate of e has also become smaller. e does not exist in the queue, so e also has to
Enter the queue. At this time, the queue The elements in are c, d, e

The first element of the team is out of the team at point c, and the relaxation operation is performed on the end points of all edges with c as the starting point (here are e, f two points), at this time the path table status is:

## This is in the shortest path table, E, F's shortest path valuation has become smaller, E exists in the queue, F does not exist. Therefore
e does not need to join the queue, and f needs to join the queue. At this time, the elements in the queue are d, e, f

The first element d of the team is clicked out Team, perform relaxation operations on the end points of all edges with d as the starting point in sequence (there is only point g here). At this time, the path table status is:

      Relaxation is unsuccessful), no new node enters the queue, the element in the queue is f, g

The first element of the team is dequeued at point f, and the end points of all edges with f as the starting point are sequentially Perform the relaxation operation (there are three points d, e, and g here). At this time, the path table status is:

##                                       #In the shortest path table, the shortest path estimates of e and g become smaller again. There is no point e in the queue, and e joins the queue. There is a point g in the queue, and g does not need to join the queue. At this time, the elements in the queue are g, e

The first element of the team, point g, is dequeued, and the relaxation operation is performed on the end points of all edges with g as the starting point (there is only point b here). At this time, the path table status is:

                                                                                                                                                                                  

In the shortest path table, the shortest path estimate of b becomes smaller again, and there is no point b in the queue , b enters the queue. At this time, the element in the queue is e, and the first element of the team b

is dequeued at point e. The relaxation operation is performed on the end points of all edges with e as the starting point in sequence (only g here is This point), at this time the path table status is:

                                                         In the shortest path table, the shortest path estimate of g has not changed (relaxation is unsuccessful). At this time, the element in the queue is b

. The first element of the queue is dequeued at point b. The end points of all edges of the starting point are relaxed in sequence (there is only point e here). At this time, the path table status is:

                       

#In the shortest path table, the shortest path estimate of e has not changed (relaxation was unsuccessful), and the queue is empty at this time

The final shortest path from a to g is １４

java code

package spfa负权路径;

import java.awt.List;
import java.util.ArrayList;
import java.util.Scanner;
public class SPFA {
	/**
	 * @param args
	 */
	public long[] result;         //用于得到第s个顶点到其它顶点之间的最短距离
	//数组实现邻接表存储
	class edge{
		public int a;//边的起点
		public int b;//边的终点
		public int value;//边的值
		public edge(int a,int b,int value){
			this.a=a;
			this.b=b;
			this.value=value;
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		SPFA spafa=new SPFA();
		Scanner scan=new Scanner(System.in);
		int n=scan.nextInt();
		int s=scan.nextInt();
		int p=scan.nextInt();
		edge[] A=new edge[p];
		for(int i=0;i<p;i++){
			int a=scan.nextInt();
			int b=scan.nextInt();
			int value=scan.nextInt();
			A[i]=spafa.new edge(a,b,value);
		}
		if(spafa.getShortestPaths(n,s,A)){
			for(int i=0;i<spafa.result.length;i++){
				System.out.println(spafa.result[i]+" ");
			}
		}else{
			System.out.println("存在负环");
		}
	}
	/*
     * 参数n:给定图的顶点个数
     * 参数s:求取第s个顶点到其它所有顶点之间的最短距离
     * 参数edge:给定图的具体边
     * 函数功能：如果给定图不含负权回路，则可以得到最终结果，如果含有负权回路，则不能得到最终结果
     */
	private boolean getShortestPaths(int n, int s, edge[] A) {
		// TODO Auto-generated method stub
		ArrayList<Integer> list = new ArrayList<Integer>();
		result=new long[n];
		boolean used[]=new boolean[n];
		int num[]=new int[n];
		for(int i=0;i<n;i++){
			result[i]=Integer.MAX_VALUE;
			used[i]=false;
		}
		result[s]=0;//第s个顶点到自身距离为0
		used[s]=true;//表示第s个顶点进入数组队
		num[s]=1;//表示第s个顶点已被遍历一次
		list.add(s); //第s个顶点入队
		while(list.size()!=0){
			int a=list.get(0);//获取数组队中第一个元素
			list.remove(0);//删除数组队中第一个元素
			for(int i=0;i<A.length;i++){
			//当list数组队的第一个元素等于边A[i]的起点时
				if(a==A[i].a&&result[A[i].b]>(result[A[i].a]+A[i].value)){
					result[A[i].b]=result[A[i].a]+A[i].value;
					if(!used[A[i].b]){
						list.add(A[i].b);
						num[A[i].b]++;
						if(num[A[i].b]>n){
							return false;
						}
						used[A[i].b]=true;//表示边A[i]的终点b已进入数组队
					}
				}
			}
			used[a]=false; //顶点a出数组对
		}
		return true;
	}
}

　

The above is the detailed content of SPFA algorithm usage tutorial. For more information, please follow other related articles on the PHP Chinese website!