深度优先和迪杰斯特拉的区别

深度优先搜索（DFS）和迪杰斯特拉算法（Dijkstra's algorithm）是两种常见的图搜索算法，它们有一些重要的区别。

深度优先搜索是一种用于遍历或搜索树或图的算法。它从起始节点开始，沿着一条路径尽可能深入地探索，直到无法继续为止，然后回溯并选择下一个未探索的路径。DFS通常使用栈来实现，以便在回溯时能够回到之前的节点。DFS在搜索图中的深层次路径时效果较好，但可能会陷入无限循环，因为它不会记住已经访问过的节点。

迪杰斯特拉算法是一种用于解决带权重的图（有向或无向）中单源最短路径问题的算法。它通过维护一个距离列表，逐步更新起始节点到其他节点的最短距离。算法初始化距离列表并将起始节点设置为0，然后选择当前距离最小的节点，并更新与其相邻节点的距离。迪杰斯特拉算法使用优先队列来选择最小距离的节点，并且会记住已经访问过的节点，以避免重复计算。

因此，深度优先搜索主要用于遍历或搜索图的结构，而迪杰斯特拉算法则用于寻找带权重的图中的最短路径。它们的应用场景和目标不同，所以它们在实际使用中有不同的优缺点。

相关问题

现需建立一个城市交通系统，可以用图的结构来表示实际交通网络，顶点表示城市，边代表城市间的交通线路，边上权值表示线路花销（单位：百元）。请用写C语言代码实现以下功能，系统具体功能需求如下： 1、从键盘输入城市及城市之间线路的信息，建立城市交通网，以下为城市之间的权值(即线路花销)a->b为15 a->c为2 a->d为12 b->e为6 c->e为8 c->f为4 d->g为3 e->g为9 f->d为5 f->g为10 g->b为4 2、输出该交通网的存储表示； 3、指定某个出发城市，对交通网进行深度优先遍历并打印结果； 4、指定某个出发城市，输出该城市到网中其他城市，花销最小的路径； 5、指定某条路线，修改路线花销。 图1.2 城市交通网 实现要求： 1、以邻接矩阵作为图的存储结构； 2、使用迪杰斯特拉算法求最短路径； 3、为该系统制定一个功能菜单，输入对应的功能编号，则执行相应功能

好的，以下是C语言代码实现城市交通系统功能：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_CITY 20
#define INF 1000000

typedef struct Graph {
    int matrix[MAX_CITY][MAX_CITY];  // 邻接矩阵
    int city_num;  // 城市数量
    char cities[MAX_CITY][20];  // 城市名称
} Graph;

// 初始化图
void init_graph(Graph *g) {
    int i, j;
    for (i = 0; i < MAX_CITY; ++i) {
        for (j = 0; j < MAX_CITY; ++j) {
            g->matrix[i][j] = INF;  // 初始化邻接矩阵
        }
    }
    g->city_num = 0;  // 初始化城市数量为0
}

// 添加城市
void add_city(Graph *g, char *city_name) {
    strcpy(g->cities[g->city_num], city_name);  // 存储城市名称
    g->city_num++;  // 城市数量加1
}

// 添加路线
void add_route(Graph *g, char *city1, char *city2, int cost) {
    int i, j, index1 = -1, index2 = -1;
    // 找到城市1和城市2的下标
    for (i = 0; i < g->city_num; ++i) {
        if (strcmp(g->cities[i], city1) == 0) {
            index1 = i;
        }
        if (strcmp(g->cities[i], city2) == 0) {
            index2 = i;
        }
    }
    // 添加路线
    g->matrix[index1][index2] = cost;
}

// 输出图的存储表示
void print_graph(Graph *g) {
    int i, j;
    printf("\n城市交通网存储表示：\n");
    printf("   ");
    for (i = 0; i < g->city_num; ++i) {
        printf("%s ", g->cities[i]);  // 输出城市名称
    }
    printf("\n");
    for (i = 0; i < g->city_num; ++i) {
        printf("%s ", g->cities[i]);  // 输出城市名称
        for (j = 0; j < g->city_num; ++j) {
            if (g->matrix[i][j] == INF) {
                printf("∞ ");  // 输出无穷大
            } else {
                printf("%d ", g->matrix[i][j]);  // 输出路线花销
            }
        }
        printf("\n");
    }
}

// 深度优先遍历
void dfs(Graph *g, int v, int visited[]) {
    int i;
    visited[v] = 1;  // 标记为已访问
    printf("%s ", g->cities[v]);  // 输出城市名称
    for (i = 0; i < g->city_num; ++i) {
        if (g->matrix[v][i] != INF && visited[i] == 0) {
            dfs(g, i, visited);  // 递归访问相邻未访问节点
        }
    }
}

// 深度优先遍历并打印结果
void dfs_search(Graph *g, char *start_city) {
    int i, start_index = -1, visited[MAX_CITY];
    // 找到出发城市的下标
    for (i = 0; i < g->city_num; ++i) {
        if (strcmp(g->cities[i], start_city) == 0) {
            start_index = i;
            break;
        }
    }
    // 初始化visited数组为0
    for (i = 0; i < g->city_num; ++i) {
        visited[i] = 0;
    }
    printf("\n从%s出发深度优先遍历结果：\n", start_city);
    dfs(g, start_index, visited);
}

// 迪杰斯特拉算法求最短路径
void dijkstra(Graph *g, int start, int end, int path[], int dist[]) {
    int i, j, min_dist, min_index, visited[MAX_CITY];
    // 初始化path数组为-1，表示没有路径
    for (i = 0; i < g->city_num; ++i) {
        path[i] = -1;
    }
    // 初始化visited数组为0，表示所有节点都未访问
    for (i = 0; i < g->city_num; ++i) {
        visited[i] = 0;
    }
    // 初始化dist数组为每个节点到起点的距离
    for (i = 0; i < g->city_num; ++i) {
        dist[i] = g->matrix[start][i];
        if (dist[i] == INF) {
            path[i] = -1;  // 如果起点到该节点没有直接路线，设置path为-1
        } else {
            path[i] = start;  // 如果起点到该节点有直接路线，设置path为起点
        }
    }
    visited[start] = 1;  // 起点已访问
    for (i = 0; i < g->city_num - 1; ++i) {
        min_dist = INF;
        min_index = -1;
        // 找到未访问节点中距离起点最近的节点
        for (j = 0; j < g->city_num; ++j) {
            if (visited[j] == 0 && dist[j] < min_dist) {
                min_dist = dist[j];
                min_index = j;
            }
        }
        visited[min_index] = 1;  // 标记为已访问
        // 更新dist数组和path数组
        for (j = 0; j < g->city_num; ++j) {
            if (visited[j] == 0 && g->matrix[min_index][j] != INF && dist[min_index] + g->matrix[min_index][j] < dist[j]) {
                dist[j] = dist[min_index] + g->matrix[min_index][j];
                path[j] = min_index;
            }
        }
    }
}

// 输出路径
void print_path(Graph *g, int start, int end, int path[]) {
    if (path[end] == -1) {
        printf("不存在从%s到%s的路线", g->cities[start], g->cities[end]);
        return;
    }
    int p[MAX_CITY], i, j = 0, k;
    p[j] = end;
    k = path[end];
    while (k != start) {
        j++;
        p[j] = k;
        k = path[k];
    }
    j++;
    p[j] = start;
    printf("\n从%s到%s的最短路径为：\n", g->cities[start], g->cities[end]);
    for (i = j; i > 0; --i) {
        printf("%s -> ", g->cities[p[i]]);
    }
    printf("%s，花费：%d百元\n", g->cities[p[0]], dist[end]);
}

// 修改路线花销
void modify_cost(Graph *g, char *city1, char *city2, int new_cost) {
    int i, j, index1 = -1, index2 = -1;
    // 找到城市1和城市2的下标
    for (i = 0; i < g->city_num; ++i) {
        if (strcmp(g->cities[i], city1) == 0) {
            index1 = i;
        }
        if (strcmp(g->cities[i], city2) == 0) {
            index2 = i;
        }
    }
    // 修改路线花销
    g->matrix[index1][index2] = new_cost;
    printf("\n%s到%s的路线花费已修改为%d百元\n", city1, city2, new_cost);
}

int main() {
    Graph g;
    char city1[20], city2[20], city_name[20], start_city[20];
    int cost, choice, start, end, i, path[MAX_CITY], dist[MAX_CITY];
    init_graph(&g);  // 初始化图
    // 添加城市
    add_city(&g, "北京");
    add_city(&g, "上海");
    add_city(&g, "广州");
    add_city(&g, "深圳");
    add_city(&g, "杭州");
    add_city(&g, "南京");
    add_city(&g, "武汉");
    add_city(&g, "成都");
    // 添加路线
    add_route(&g, "北京", "上海", 15);
    add_route(&g, "北京", "广州", 2);
    add_route(&g, "北京", "武汉", 12);
    add_route(&g, "上海", "杭州", 6);
    add_route(&g, "广州", "杭州", 8);
    add_route(&g, "广州", "成都", 4);
    add_route(&g, "武汉", "南京", 3);
    add_route(&g, "杭州", "深圳", 9);
    add_route(&g, "杭州", "南京", 5);
    add_route(&g, "南京", "成都", 10);
    add_route(&g, "成都", "上海", 4);
    while (1) {
        printf("\n城市交通系统功能菜单：\n");
        printf("1. 输出城市交通网存储表示\n");
        printf("2. 指定出发城市，深度优先遍历并打印结果\n");
        printf("3. 指定出发城市和终点城市，输出最短路径和花销\n");
        printf("4. 修改路线花销\n");
        printf("5. 退出系统\n");
        printf("请选择功能编号：");
        scanf("%d", &choice);
        switch (choice) {
            case 1:
                print_graph(&g);
                break;
            case 2:
                printf("请输入出发城市：");
                scanf("%s", start_city);
                dfs_search(&g, start_city);
                break;
            case 3:
                printf("请输入出发城市和终点城市：");
                scanf("%s %s", city1, city2);
                start = -1;
                end = -1;
                // 找到出发城市和终点城市的下标
                for (i = 0; i < g.city_num; ++i) {
                    if (strcmp(g.cities[i], city1) == 0) {
                        start = i;
                    }
                    if (strcmp(g.cities[i], city2) == 0) {
                        end = i;
                    }
                }
                if (start == -1 || end == -1) {
                    printf("城市不存在！");
                } else {
                    dijkstra(&g, start, end, path, dist);
                    print_path(&g, start, end, path, dist);
                }
                break;
            case 4:
                printf("请输入路线的起点、终点和新的花销：");
                scanf("%s %s %d", city1, city2, &cost);
                modify_cost(&g, city1, city2, cost);
                break;
            case 5:
                printf("已退出城市交通系统\n");
                return 0;
            default:
                printf("输入错误，请重新选择！\n");
                break;
        }
    }
}

注意事项：

1. 代码中使用了邻接矩阵作为图的存储结构；
2. 深度优先遍历和迪杰斯特拉算法的实现可能需要些许时间来理解；
3. 代码中使用了一些全局变量，这不是一个很好的实践，但是为了简化代码，这里先这样处理。在实际项目开发中，需要尽量避免使用全局变量。

采用BFS和DFS求解带权图最短路径，使用C++

在C++中，使用BFS（广度优先搜索）和DFS（深度优先搜索）来求解带权图的最短路径，一般我们会选择BFS，因为它是保证找到最短路径的有效方法。这里我会展示一个简单的BFS实现，假设我们已经有了一个邻接矩阵`adjMatrix`来表示图，以及一个函数`getWeight(i, j)`获取从城市i到j的边的权重。

首先，我们假设所有的权重都是非负的，因为负权重的情况需要使用其他算法，比如迪杰斯特拉(Dijkstra)或Floyd-Warshall。

以下是使用BFS的C++代码示例：

#include <vector>
#include <queue>
using namespace std;

// 获取权重
int getWeight(int i, int j, vector<vector<int>>& adjMatrix) {
    // 实际的实现依赖于您的图模型，此处仅作为占位符
    return adjMatrix[i][j];
}

// 广度优先搜索
pair<int, vector<int>> bfs(vector<vector<int>>& adjMatrix, int start, int end) {
    vector<bool> visited(adjMatrix.size(), false);
    vector<int> distances(adjMatrix.size(), INT_MAX); // 初始化所有距离为最大值
    distances[start] = 0; // 起点的距离为0

    queue<int> q;
    q.push(start);

    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        for (int neighbor : adjMatrix[curr]) { // 遍历邻居
            int weight = getWeight(curr, neighbor, adjMatrix);
            if (visited[neighbor] || weight > distances[curr]) continue;

            distances[neighbor] = distances[curr] + weight;
            q.push(neighbor);
        }

        visited[curr] = true;
    }

    if (distances[end] == INT_MAX) return {INT_MAX, {}}; // 如果未找到路径，则返回无穷大

    vector<int> path;
    for (int node = end; node != start; node = parent[node]) { // 逆序构建路径
        path.push_back(node);
    }
    path.push_back(start); // 包含起始节点
    reverse(path.begin(), path.end());

    return {distances[end], path};
}

int main() {
    // 初始化邻接矩阵和其他变量...
    auto result = bfs(adjMatrix, A, E); // A是起始城市，E是目标城市
    cout << "Shortest path distance: " << result.first << endl;
    cout << "Path: ";
    for (auto& city : result.second) {
        cout << city << " -> ";
    }
    cout << "A" << endl;
    return 0;
}