How to implement the shortest path algorithm of a graph using java

How to use Java to implement the shortest path algorithm for graphs?

Title: Use Dijkstra's algorithm to solve the shortest path problem of graphs

Introduction:
Graph is an important data structure in discrete mathematics and is widely used in the fields of information science and computer science. The shortest path algorithm for graphs is one of the key technologies to solve many practical problems, such as network routing, urban planning, etc. This article will introduce how to use the Java programming language to implement the famous Dijkstra algorithm to solve the shortest path problem of the graph.

1. Algorithm principle:

Dijkstra's algorithm is a greedy algorithm used to find the shortest path from a starting point to other vertices in a weighted graph. The basic idea is to start from the starting point, select the vertex of the current shortest path each time, and update the shortest paths of its adjacent vertices. This process is repeated until the target vertex is reached, or all vertices have been visited.

2. Algorithm steps:

1. Initialize the distance array dist[] and the shortest path array path[], initialize the distance from the starting point to other vertices to infinity, and the distance from the starting point to itself is 0, the shortest path array is initialized to empty;
2. Add the starting point to the collection visited;

3. Starting from the starting point, select the unvisited vertex v in turn, and update the starting point to v The shortest path:

   • If the distance from the starting point to vertex w via vertex v is shorter than the distance from the starting point directly to vertex w, then update dist[w] to dist[v] side length (v, w), and add v to path[w];
4. Repeat step 3 until the target vertex is visited or all vertices have been visited;
5. According to the shortest The path array path[] builds the shortest path in reverse.

3. Java code implementation:

The following is a code example of using Java language to implement Dijkstra's algorithm:

import java.util.*;

public class Dijkstra {
    private static final int INF = Integer.MAX_VALUE;  // 定义无穷大

    public static void dijkstra(int[][] graph, int start) {
        int numVertices = graph[0].length;

        int[] dist = new int[numVertices];  // 存储最短路径的数组
        boolean[] visited = new boolean[numVertices]; // 记录顶点是否访问过

        for (int i = 0; i < numVertices; i++) {
            dist[i] = INF;  // 初始化距离数组为无穷大
            visited[i] = false; // 初始化访问数组为false
        }

        dist[start] = 0;  // 起点到自身的距离为0

        for (int count = 0; count < numVertices - 1; count++) {
            int u = getMinDistVertex(dist, visited);  // 选择当前最短路径的顶点

            visited[u] = true;  // 标记该顶点已访问

            for (int v = 0; v < numVertices; v++) {
                if (!visited[v] && graph[u][v] != 0 && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];  // 更新最短路径
                }
            }
        }

        printSolution(dist);  // 打印最短路径
    }

    private static int getMinDistVertex(int[] dist, boolean[] visited) {
        int minDist = INF;
        int minDistVertex = -1;

        int numVertices = dist.length;

        for (int v = 0; v < numVertices; v++) {
            if (!visited[v] && dist[v] <= minDist) {
                minDist = dist[v];
                minDistVertex = v;
            }
        }

        return minDistVertex;
    }

    private static void printSolution(int[] dist) {
        int numVertices = dist.length;

        System.out.println("Vertex          Distance from Start");

        for (int i = 0; i < numVertices; i++) {
            System.out.println(i + "          " + dist[i]);
        }
    }

    public static void main(String[] args) {
        int[][] graph = {
                {0, 4, 0, 0, 0, 0, 0, 8, 0},
                {4, 0, 8, 0, 0, 0, 0, 11, 0},
                {0, 8, 0, 7, 0, 4, 0, 0, 2},
                {0, 0, 7, 0, 9, 14, 0, 0, 0},
                {0, 0, 0, 9, 0, 10, 0, 0, 0},
                {0, 0, 4, 0, 10, 0, 2, 0, 0},
                {0, 0, 0, 14, 0, 2, 0, 1, 6},
                {8, 11, 0, 0, 0, 0, 1, 0, 7},
                {0, 0, 2, 0, 0, 0, 6, 7, 0}
        };

        dijkstra(graph, 0);
    }
}

4. Algorithm analysis:

The time complexity of Dijkstra's algorithm is O(V^2), where V is the number of vertices of the graph. In cases where the graph is larger or has a larger number of edges, the efficiency of the algorithm may be lower. To improve efficiency, data structures such as priority queues can be used to optimize Dijkstra's algorithm.

Conclusion:
This article introduces how to use Java language to implement Dijkstra's algorithm to solve the shortest path problem of graphs. This algorithm can find the shortest path from the starting point to other vertices in a directed or undirected graph, and achieves an efficient solution by updating the shortest path array. Readers can further explore and gain a deeper understanding of the shortest path algorithm for graphs based on the sample code in this article.

The above is the detailed content of How to implement the shortest path algorithm of a graph using java. For more information, please follow other related articles on the PHP Chinese website!