Graph Algorithm Series: Shortest Path in Computational Graph

[[398324]]

This article is reprinted from the WeChat public account "Beta Learns JAVA", the author is Silently9527. Please contact the Beta Learns JAVA public account to reprint this article.

Preface

In the previous two articles, we used depth-first search to find a path from vertex v to vertex w in the graph. However, depth-first search has a lot to do with vertex input, and the path found is not necessarily the shortest. Usually, we often need to find the shortest path in the graph, such as map function. Here we need to use the breadth-first search algorithm.

Breadth-First Search

Still use the previously defined path finding API

 public class Paths {
    Paths(Graph graph, int s); 
     
 boolean hasPathTo( int v); //Determine whether there is a path from s->v 
     
 Iterable< Integer > pathTo( int v); //If the path exists, return the path
 }

In breadth-first search, in order to find the shortest path, we need to traverse all vertices in the order of the starting point, instead of using recursion to achieve it; the idea of ​​the algorithm is:

• Use a queue to store vertices that have been marked but whose adjacency lists have not yet been traversed.
• Take the next vertex v from the queue and mark it
• Add all unmarked vertices adjacent to v to the queue

In this algorithm, in order to save the path, we still need to use an edge array edgeTo[] and use a parent link tree to represent the shortest path from the root node to all connected vertices.

 public class BreadthFirstPaths {
 private boolean marked[];
 private int [] edgeTo;
 private int s;
    private Queue< Integer > queue = new LinkedListQueue<>(); 
 
 public BreadthFirstPaths(Graph graph, int s) {
 this.s = s;
        this.marked = new boolean[graph.V()];
        this.edgeTo = new int [graph.V()]; 
 
 bfs(graph, s);
 } 
 
    private void bfs(Graph graph, int s) {
        this.marked[s] = true ;
        this.queue.enqueue(s);
        while (!this.queue.isEmpty()) {
 Integer v = this.queue.dequeue();
 for ( int w : graph.adj(v)) {
                if (!this.marked[w]) {
                    this.marked[w] = true ;
                    this.edgeTo[w] = v;
                    this.queue.enqueue(w);
 }
 }
 } 
 
 
 } 
 
 public boolean hasPathTo( int v) {
 return this.marked[v];
 } 
 
 public Iterable< Integer > pathTo( int v) {
 if (!hasPathTo(v)) {
 throw new IllegalStateException( "s cannot reach v" );
 }
        Stack< Integer > stack = new LinkedListStack<>();
 stack.push(v);
        while (edgeTo[v] != s) {
            stack.push(edgeTo[v]);
 v = edgeTo[v];
 }
 stack.push(s);
 return stack;
 }
 }

Take the following figure as a column to see the running track of breadth-first search

Unit test code:

 @Test
 public void test() {
    Graph graph = new Graph(8);
 graph.addEdge(0, 1);
 graph.addEdge(0, 2);
 graph.addEdge(0, 5);
 graph.addEdge(1, 3);
 graph.addEdge(2, 4);
 graph.addEdge(4, 3);
 graph.addEdge(5, 3);
 graph.addEdge(6, 7); 
 
    BreadthFirstPaths paths = new BreadthFirstPaths(graph, 0);
    System. out .println(paths.hasPathTo(5));
    System. out .println(paths.hasPathTo(2));
    System. out .println(paths.hasPathTo(6)); 
 
    paths.pathTo(5).forEach(System. out ::print);
 System.out.println( ) ;
    paths.pathTo(4).forEach(System. out ::print);
 System.out.println( ) ;
    paths.pathTo(2).forEach(System. out ::print);
 System.out.println( ) ;
    paths.pathTo(3).forEach(System. out ::print); 
 
 }

The execution results are consistent with the running trajectory we analyzed

Symbol diagram

The graph algorithms that we have learned in recent articles all use numbers as vertices because it is very simple and convenient to implement these algorithms with numbers. However, in actual scenarios, characters are usually used as vertices instead of numbers, such as: locations on a map, and the relationship between movies and actors.

In order to meet the actual scenario, we only need to make a mapping between numbers and strings. At this time, we will think of the map implemented in the previous article (map is implemented through binary tree, red-black tree, hash table, etc., interested students can check it out), and use Map to maintain the mapping relationship between strings and numbers.

 public interface SymbolGraph {
 boolean contains (String key ); //Judge whether a vertex exists 
 
 int   index (String key ); //Return the corresponding digital vertex by name 
 
 String name ( int v); //Return the corresponding character name through the digital vertex 
 
 Graph graph();
 }

Implementation ideas:

• Use Map to save string-number mapping, key is string, value is number
• Use an array to reverse the mapping from numbers to strings, where the array subscripts correspond to the numerical vertices and the values ​​correspond to the string names
• Assume that the vertices and edges of the constructed graph are represented by strings, such as: a,b,c,d\nb,a,h,l,p\ng,s,z. The first string of each segment separated by \n represents the vertex v, and the following represents the adjacent vertices connected to the vertex v.

The actual process can be determined according to the specific situation. It does not necessarily have to be this kind of string. It can come from a database or a network request.

The code is implemented as follows:

 public class SymbolGraph {
    private Map<String, Integer > map = new RedBlack23RedBlackTreeMap<>();
 private String[] keys;
 private Graph graph; 
 
 public SymbolGraph(String text) {
        Arrays.stream(text.split( "\n" )).forEach(line -> {
            String[] split = line.split( "," );
 for ( int i = 0; i < split.length; i++) {
                map.put(split[i], i);
 }
 }); 
 
        this.keys = new String[map. size ()];
        map.keys().forEach( key -> {
            this.keys[this.map.get( key )] = key ;
 }); 
 
        this.graph = new Graph(this.keys.length);
        Arrays.stream(text.split( "\n" )).forEach(line -> {
            String[] split = line.split( "," );
 int v = this.map.get(split[0]);
 for ( int i = 1; i < split.length; i++) {
                this.graph.addEdge(v, this.map.get(split[i]));
 }
 }); 
         
 } 
 
 public boolean contains (String key ) {
 return map.contains ( key ) ;
 } 
 
 public   int   index (String key ) {
 return map.get( key );
 } 
 
 public String name ( int   index ) {
 return this.keys[ index ];
 } 
 
 public Graph graph() {
 return this.graph;
 } 
 
 public   static void main(String[] args) {
        System. out .println(Arrays.toString( "323\n2323" .split( "\n" )));
 }
 }

All source code in this article has been put into the github repository: https://github.com/silently9527/JavaCore