图优先搜素算法求从一个城市A到另一个城市H的路径

假设有如下的地图，其中每个城市用字母表示，城市之间的距离用数字表示：

        5       4       3       2
    A-------B-------C-------D-------E
    |               |               |
   14               9               5
    |               |               |
    F-------G-------H-------I-------J
        9       7       8       5

我们可以使用图优先搜索算法来找到从城市A到城市H的路径。这里我们选择启发式函数为直线距离，即从当前城市到目标城市的直线距离。我们可以使用一个优先队列来存储待扩展的节点，每次从队列中取出距离目标城市最近的节点进行扩展。具体步骤如下：

1. 初始化优先队列，将起始城市A加入队列，并将其到起点的距离设为0。

2. 从优先队列中取出距离目标城市H最近的节点，即城市A，并将其标记为已访问。

3. 对于城市A可以到达的所有未访问过的邻居节点，计算它们到目标城市H的直线距离，并将它们加入优先队列中。

4. 重复步骤2和3，直到取出的节点为目标城市H，或者优先队列为空。

5. 如果找到了目标城市H，回溯路径即可得到从城市A到城市H的路径。

根据上述步骤，我们可以找到从城市A到城市H的路径为：A -> F -> G -> H。

相关问题

写一段代码使用Dijkstra算法找从一个城市到另一个城市的最短路径

以下是使用Dijkstra算法找从一个城市到另一个城市的最短路径的Python代码示例：

import heapq

def dijkstra(graph, start, end):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    pq = [(0, start)]
    while pq:
        current_distance, current_vertex = heapq.heappop(pq)
        if current_vertex == end:
            return distances[end]
        if current_distance > distances[current_vertex]:
            continue
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

# 示例数据
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1, 'E': 3},
    'E': {'D': 3}
}

start = 'A'
end = 'E'
shortest_distance = dijkstra(graph, start, end)
print(f'The shortest distance from {start} to {end} is {shortest_distance}')

在这个示例中，我们定义了一个名为`dijkstra`的函数，它接受三个参数：一个表示图的字典、起始点和目标点。函数使用堆优化的Dijkstra算法来计算最短路径。我们还定义了一个示例数据`graph`，它是一个包含五个节点的图。最后，我们调用`dijkstra`函数并输出结果。

写一段代码使用Dijkstra算法找从一个城市到另一个城市的最短路径c语言

以下是使用 Dijkstra 算法在 C 语言中找到从一个城市到另一个城市的最短路径的示例代码：

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>

#define V 6 // 假设图中有 6 个顶点

int graph[V][V] = { // 图的邻接矩阵表示
    {0, 4, 0, 0, 0, 0},
    {4, 0, 8, 0, 0, 0},
    {0, 8, 0, 7, 0, 4},
    {0, 0, 7, 0, 9, 14},
    {0, 0, 0, 9, 0, 10},
    {0, 0, 4, 14, 10, 0}
};

// 返回未处理的顶点中距离起点最近的顶点的下标
int minDistance(int dist[], bool sptSet[]) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;
    return min_index;
}

// 打印最短路径
void printPath(int parent[], int j) {
    if (parent[j] == -1)
        return;
    printPath(parent, parent[j]);
    printf("%d ", j);
}

// 打印结果
void printSolution(int dist[], int n, int parent[]) {
    int src = 0;
    printf("Vertex\t Distance\tPath");
    for (int i = 1; i < V; i++) {
        printf("\n%d -> %d \t\t %d\t\t%d ", src, i, dist[i], src);
        printPath(parent, i);
    }
}

// 使用 Dijkstra 算法找到从源点 src 到其他所有顶点的最短距离
void dijkstra(int src) {
    int dist[V]; // 存储从源点到其他所有顶点的最短距离
    bool sptSet[V]; // sptSet[i] 表示是否已经处理过顶点 i
    int parent[V]; // parent[i] 存储从源点到顶点 i 的最短路径中顶点 i 的父节点
    for (int i = 0; i < V; i++) {
        parent[0] = -1;
        dist[i] = INT_MAX;
        sptSet[i] = false;
    }
    dist[src] = 0;
    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;
        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                parent[v] = u;
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
    printSolution(dist, V, parent);
}

int main() {
    dijkstra(0); // 从第 0 个顶点开始
    return 0;
}

在这个例子中，我们使用邻接矩阵作为图的表示方式，其中 `graph[i][j]` 表示从顶点 i 到顶点 j 的边的权重。我们从第 0 个顶点（源点）开始使用 Dijkstra 算法，计算出从源点到其他所有顶点的最短距离，并打印结果。

注意，这里的代码只是一个简单的示例，实际应用中可能需要根据具体情况进行修改。