以下是一个使用迪杰斯特拉算法求最短路径的校园导航的C语言代码示例:

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

#define MAX_VERTICES 100
#define INFINITY 99999

typedef struct {
    int weight;
    bool visited;
    int prev;
} Vertex;

int graph[MAX_VERTICES][MAX_VERTICES];
Vertex vertices[MAX_VERTICES];
int numVertices;

// 初始化图
void initGraph() {
    int i, j;
    for (i = 0; i < MAX_VERTICES; i++) {
        for (j = 0; j < MAX_VERTICES; j++) {
            graph[i][j] = (i == j) ? 0 : INFINITY;
        }
    }
}

// 添加边
void addEdge(int start, int end, int weight) {
    graph[start][end] = weight;
    graph[end][start] = weight;
}

// 寻找最短路径
void dijkstra(int start) {
    int i, j, minIndex, minDist;
    
    // 初始化顶点信息
    for (i = 0; i < numVertices; i++) {
        vertices[i].weight = INFINITY;
        vertices[i].visited = false;
        vertices[i].prev = -1;
    }
    
    vertices[start].weight = 0;
    
    for (i = 0; i < numVertices; i++) {
        minIndex = -1;
        minDist = INFINITY;
        
        // 找到未访问的最近顶点
        for (j = 0; j < numVertices; j++) {
            if (!vertices[j].visited && vertices[j].weight < minDist) {
                minIndex = j;
                minDist = vertices[j].weight;
            }
        }
        
        if (minIndex == -1) {
            break;
        }
        
        vertices[minIndex].visited = true;
        
        // 更新与最近顶点相邻的顶点的权值
        for (j = 0; j < numVertices; j++) {
            if (!vertices[j].visited && graph[minIndex][j] != INFINITY) {
                int newDist = vertices[minIndex].weight + graph[minIndex][j];
                if (newDist < vertices[j].weight) {
                    vertices[j].weight = newDist;
                    vertices[j].prev = minIndex;
                }
            }
        }
    }
}

// 打印最短路径
void printShortestPath(int start, int end) {
    int path[MAX_VERTICES];
    int pathLength = 0;
    int i = end;
    
    while (i != start) {
        path[pathLength++] = i;
        i = vertices[i].prev;
    }
    
    printf("最短路径为:");
    printf("%d", start);
    
    for (i = pathLength - 1; i >= 0; i--) {
        printf(" -> %d", path[i]);
    }
    
    printf("\n");
}

int main() {
    initGraph();
    
    // 添加校园地点和路径信息
    numVertices = 8;
    addEdge(0, 1, 5);
    addEdge(0, 2, 10);
    addEdge(1, 3, 8);
    addEdge(1, 4, 4);
    addEdge(2, 3, 3);
    addEdge(2, 5, 6);
    addEdge(3, 4, 7);
    addEdge(3, 5, 2);
    addEdge(4, 6, 5);
    addEdge(5, 6, 9);
    addEdge(5, 7, 1);
    addEdge(6, 7, 12);
    
    dijkstra(0);
    
    printShortestPath(0, 7);
    
    return 0;
}

上述代码中,我们通过定义一个二维数组来表示校园地点之间的路径,并使用迪杰斯特拉算法来计算最短路径。initGraph()函数用于初始化图,addEdge()函数用于添加边,dijkstra()函数用于寻找最短路径,printShortestPath()函数用于打印最短路径。

main()函数中,我们通过添加校园地点和路径信息来构建图,并调用dijkstra()函数来计算最短路径,最后调用printShortestPath()函数来打印最短路径。

请注意,上述代码只是一个示例,具体的校园地点和路径信息需要根据实际情况进行修改

运用数据结构知识编写一个校园以江西财经大学麦庐园为例导航的C语言代码要求运用迪杰斯特拉算法求最短路径。

原文地址: https://www.cveoy.top/t/topic/h0PS 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录