设计无权值广度优先算法”算法和“有权值广度优先算法”2个算法。

1. 无权值广度优先算法

无权值广度优先算法（Unweighted Breadth-First Search，简称BFS）是一种基于图论的搜索算法，用于寻找从起点到终点的最短路径。该算法从起点开始，依次将与其相邻的所有节点加入队列中，然后从队列中取出队首节点，继续将其相邻的节点加入队列中，并标记已访问过的节点，直到找到终点或队列为空。

算法步骤：

1. 将起点加入队列，标记已访问过的节点。
2. 从队列中取出队首节点，遍历其相邻节点，将未访问过的节点加入队列，标记已访问过的节点。
3. 重复步骤2，直到找到终点或队列为空。

2. 有权值广度优先算法

有权值广度优先算法（Weighted Breadth-First Search，简称W-BFS）也是基于图论的搜索算法，用于寻找从起点到终点的最短路径，但与无权值广度优先算法不同的是，它考虑了边权重的影响。在每一次遍历相邻节点时，会比较当前节点与相邻节点之间的边权重，并根据权重值进行排序，然后将排序后的节点加入队列。

算法步骤：

1. 将起点加入队列，标记已访问过的节点。
2. 从队列中取出队首节点，遍历其相邻节点，计算当前节点与相邻节点之间的边权重并将其加入队列。
3. 对队列中的节点按照边权重进行排序，然后将排序后的节点依次加入队列，标记已访问过的节点。
4. 重复步骤2和步骤3，直到找到终点或队列为空。

需要注意的是，无权值广度优先算法和有权值广度优先算法都只适用于无向图或者有向无环图。对于有环图，需要使用其他算法才能找到最短路径。

相关问题

城市最短路径问题无权值广度优先算法java实现

以下是无权值广度优先算法Java实现：

import java.util.LinkedList;
import java.util.Queue;

public class ShortestPath {
    private int[][] graph;
    private int source;
    private int destination;
    private boolean[] visited;
    private int[] distance;
    private int[] predecessor;

    public ShortestPath(int[][] graph, int source, int destination) {
        this.graph = graph;
        this.source = source;
        this.destination = destination;
        this.visited = new boolean[graph.length];
        this.distance = new int[graph.length];
        this.predecessor = new int[graph.length];
        for (int i = 0; i < graph.length; i++) {
            visited[i] = false;
            distance[i] = Integer.MAX_VALUE;
            predecessor[i] = -1;
        }
    }

    public void bfs() {
        Queue<Integer> queue = new LinkedList<>();
        visited[source] = true;
        distance[source] = 0;
        queue.add(source);

        while (!queue.isEmpty()) {
            int current = queue.poll();
            for (int neighbor = 0; neighbor < graph.length; neighbor++) {
                if (graph[current][neighbor] == 1 && !visited[neighbor]) {
                    visited[neighbor] = true;
                    distance[neighbor] = distance[current] + 1;
                    predecessor[neighbor] = current;
                    queue.add(neighbor);
                }
            }
        }
    }

    public void printPath() {
        if (distance[destination] == Integer.MAX_VALUE) {
            System.out.println("No path found!");
            return;
        }

        int current = destination;
        String path = "";
        while (current != source) {
            path = "->" + current + path;
            current = predecessor[current];
        }
        path = source + path;
        System.out.println("Shortest path: " + path);
        System.out.println("Shortest distance: " + distance[destination]);
    }

    public static void main(String[] args) {
        int[][] graph = {
                {0, 1, 1, 0, 0},
                {1, 0, 1, 1, 0},
                {1, 1, 0, 1, 1},
                {0, 1, 1, 0, 1},
                {0, 0, 1, 1, 0}
        };
        int source = 0;
        int destination = 4;
        ShortestPath shortestPath = new ShortestPath(graph, source, destination);
        shortestPath.bfs();
        shortestPath.printPath();
    }
}

其中，`graph` 表示无向图的邻接矩阵，`source` 和 `destination` 分别表示起点和终点。`visited` 数组表示该节点是否已经被访问过，`distance` 数组表示该节点到起点的距离，`predecessor` 数组表示该节点的前驱节点。在 `bfs` 方法中，首先将起点标记为已访问并加入队列，然后遍历队列中的节点的邻居节点，如果邻居节点未被访问过，则将其标记为已访问并加入队列，同时更新邻居节点的距离和前驱节点。在 `printPath` 方法中，如果终点的距离为最大值，则说明不存在从起点到终点的路径，否则，根据前驱节点依次回溯路径。

广度优先和A*算法比较

广度优先搜索和A*算法都是常用的图搜索算法，但它们的目标和实现方式不同。

广度优先搜索是一种盲目搜索算法，它从起始节点开始，依次考虑所有与当前节点相邻的节点，直到找到目标节点。广度优先搜索通常用于在无权图中搜索最短路径或者在状态空间中搜索最少步骤的解决方案。然而，广度优先搜索不能保证找到最优解，因为它只考虑了到达目标节点的距离，没有考虑到其他因素。

A*算法是一种启发式搜索算法，它综合了广度优先搜索和贪心算法的优点，通过对每个节点进行评估函数的计算，找到距离目标节点最近的节点。评估函数通常包括从起始节点到当前节点的距离和从当前节点到目标节点的估计距离。A*算法在搜索过程中，优先考虑距离目标节点更近的节点，因此更容易找到最优解。

总的来说，广度优先搜索适用于无权图中的最短路径问题，而A*算法适用于带权图或状态空间中的最优解问题。但是，A*算法需要对评估函数进行设计和优化，否则可能会出现搜索效率低下的情况。