2021.05.11

Learning in the geek time [time.geekbang.org/column/arti…].

We use the Vertexes array to record the distance from the initial vertex to each vertex (dist). Initially, we initialized dist to infinity for all vertices (that is, integer.max_value in the code). We initialize the dist value of the starting vertex to 0 and place it in the priority queue.

We take minVertex, the vertex with the smallest DIST, from the priority queue and look at all the vertices reachable by this vertex (nextVertex in the code). If the dist value of minVertex plus the weight w of the edge between minVertex and nextVertex is less than the dist value of nextVertex, that is, there is another shorter path, It goes through minVertex to nextVertex. So let’s update dist from nextVertex to Dist from minVertex plus w. Next, we add nextVertex to the priority queue. This process is repeated until the terminating vertex T is found or the queue is empty.

The predecessor array is used to restore the shortest path, which records the precursor vertices of each vertex.

The inQueue array is designed to avoid adding a vertex to the priority queue more than once. After we update the dist value of a vertex, if that vertex is already in the priority queue, don’t add it again.

Private class PriorityQueue {// Build a private class PriorityQueue according to vertex. Dist private vertex [] nodes; private int count; public PriorityQueue(int v) { this.nodes = new Vertex[v+1]; this.count = v; Public void add(Vertex poll) {} public void add(Vertex poll) {} public void add(Vertex poll) {} Time complexity O(logn). public void update(Vertex vertex) { } public boolean isEmpty() { } }

Public void dijkstra(int s, int t) {public void dijkstra(int s, int t) {[] predecessor = new int[this.v]; Vertexes = new Vertex[this.v]; vertexes = new Vertex[this.v]; for (int i = 0; i < this.v; ++i) { vertexes[i] = new Vertex(i, Integer.MAX_VALUE); } PriorityQueue queue = new PriorityQueue(this.v); Boolean [] inqueue = new Boolean [this.v]; Dist = 0; vertexes[s]. Dist = 0; queue.add(vertexes[s]); inqueue[s] = true; while (! queue.isEmpty()) { Vertex minVertex= queue.poll(); If (minVertex. Id == t) break; // for (int I = 0; i < adj[minVertex.id].size(); ++i) { Edge e = adj[minVertex.id].get(i); Vertex nextVertex = vertexes[e.id]; Dist: minVertex–>nextVertex if (minVertex. Dist + e.w < nextVertex. Dist) {minVertex–>nextVertex if (minVertex. Dist + e.w < nextVertex. Dist) {minVertex–>nextVertex if (minVertex. Dist + e.w < nextVertex. Dist) {minVertex–>nextVertex if (minVertex + e.w; predecessor[nextVertex.id] = minVertex.id; if (inqueue[nextVertex.id] == true) { queue.update(nextVertex); } else {queue. Add (nextVertex); inqueue[nextVertex.id] = true; }}}} // Print the shortest path system.out.print (s); print(s, t, predecessor); }

private void print(int s, int t, int[] predecessor) { if (s == t) return; print(s, predecessor[t], predecessor); System.out.print(“->” + t); Dijkstra time complexity:

The while loop will execute at most V times, and the inner for loop will not exceed the number of edges in the graph, E. The priority queues inside the for loop are implemented using the heap and are all O(logV) in time. So, the time of the entire code is order E logV.

 

  1. Prim

Prim algorithm uses greedy strategy, relatively simple, directly on the code to understand.

public static void primTree() { buildGraph(); Vertex start = vertexList.get(0); newVertex.add(start); for (int n = 0; n < vertexList.size() - 1; n++) { Vertex temp = new Vertex(start.key); Edge tempedge = new Edge(start, start, 1000); for (Vertex v : newVertex) { for (Edge e : EdgeQueue) { if (e.start == v && ! containVertex(e.end)) { if (e.key < tempedge.key) { temp = e.end; tempedge = e; } } } } newVertex.add(temp); } Iterator it = newVertex.iterator(); while (it.hasNext()) { Vertex v = (Vertex) it.next(); System.out.println(v.key); } } public static boolean containVertex(Vertex vte) { for (Vertex v : newVertex) { if (v.key.equals(vte.key)) return true; } return false; }Copy the code

Prim time complexity:

In the realization of adjacency matrix, it takes O(V^2) running time to find all the least weighted edges.