写一段最短路径搜索c语言代码

### 回答1：

我们可以使用广度优先搜索（BFS）来解决最短路径搜索问题。下面是一段用C语言编写的最短路径搜索示例代码： #include <stdio.h>
#include <stdlib.h> #define MAX 100 /* 边的定义 */
struct Edge
{
int src, dest, weight;
}; /* 图的定义 */
struct Graph
{
int V, E;
struct Edge* edge;
}; /* 创建图 */
struct Graph* createGraph(int V, int E)
{
struct Graph* graph =
(struct Graph*) malloc( sizeof(struct Graph) );
graph->V = V;
graph->E = E;
graph->edge =
(struct Edge*) malloc( graph->E * sizeof( struct Edge ) );
return graph;
} /* 最短路径搜索函数 */
void shortestPath(struct Graph* graph, int src)
{
int V = graph->V;
int dist[V];
int i, u, count, w, flag[V], min;
for (i = 0; i < V; i++)
dist[i] = MAX, flag[i] = 0;
dist[src] = 0;
for (count = 0; count < V-1; count++)
{
min = MAX;
for (i = 0; i < V; i++)
if (dist[i] < min && !flag[i])
min = dist[i], u = i;
flag[u] = 1;
for (i = 0; i < V; i++)
if ((dist[u] + graph->edge[i].weight) < dist[i] && !flag[i])
dist[i] = dist[u] + graph->edge[i].weight;
}
printf("最短路径：\n");
for (i = 0; i < V; i++)
printf("%d \t\t %d\n", i, dist[i]);
} /* 主函数 */
int main()
{
int V = 9;
int E = 14;
struct Graph* graph = createGraph(V, E);
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = 4;
graph->edge[1].src = 0;
graph->edge[1].dest = 7;
graph->edge[1].weight = 8;
graph->edge[2].src = 1;
graph->edge[2].dest = 2;
graph->edge[2].weight = 8;
graph->edge[3].src = 1;
graph->edge[3].dest = 7;
graph->edge[3].weight = 11;
graph->edge[4].src = 2;
graph->edge[4].dest = 3;
graph->edge[4].weight = 7;
graph->edge[5].src = 2;
graph->edge[5].dest = 8;
graph->edge[5].weight = 2;
graph->edge[6].src = 2;
graph->edge[6].dest = 5;
graph->edge[6].weight = 4;
graph->edge[7].src = 3;
graph->edge[7].dest = 4;
graph->edge[7].weight = 9;
graph->edge[8].src = 3;
graph->edge[8].dest = 5;
graph->edge[8].weight = 14;
graph->edge[9].src = 4;
graph->edge[9].dest = 5;
graph->edge[9].weight = 10;
graph->edge[10].src = 5;
graph->edge[10].dest = 6;
graph->edge[10].weight = 2;
graph->edge[11].src = 6;
graph->edge[11].dest = 7;
graph->edge[11].weight = 1;
graph->edge[12].src = 6;
graph->edge[12].dest = 8;
graph->edge[12].weight = 6;
graph->edge[13].src = 7;
graph->edge[13].dest = 8;
graph->edge[13].weight = 7;
shortestPath(graph, 0);
return 0;
}

### 回答2：
下面是一个简单的用于寻找最短路径的C语言代码示例：

#include <stdio.h>
#include <stdbool.h>
#define MAX_SIZE 100
 
int graph[MAX_SIZE][MAX_SIZE];
int dist[MAX_SIZE];
bool visited[MAX_SIZE];
int parent[MAX_SIZE];
int vertices;

int minDistance(){
    int min = INT_MAX, minIndex;
    for (int v = 0; v < vertices; v++){
       if (visited[v] == false && dist[v] <= min){
           min = dist[v], minIndex = v;
       }
    } 
    return minIndex;
}

void printPath(int j){
    if (parent[j] == -1){
        return;
    }
    printPath(parent[j]);
    printf("%d ", j);
}
 
void printSolution(int src){
    printf("Vertex\tDistance\tPath");
    for (int i = 0; i < vertices; i++){
        if (i != src){
            printf("\n%d -> %d\t\t%d\t\t%d ", src, i, dist[i], src);
            printPath(i);
        }
    }
}

void dijkstra(int src){
    for (int i = 0; i < vertices; i++){
        dist[i] = INT_MAX;
        visited[i] = false;
    }
    parent[src] = -1;
    dist[src] = 0;
    for (int count = 0; count < vertices - 1; count++){
        int u = minDistance();
        visited[u] = true;
        for (int v = 0; v < vertices; v++){
            if (!visited[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(src);
}
 
int main(){
    vertices = 6;
    // 初始化图
    for (int i = 0; i < vertices; i++){
        for (int j = 0; j < vertices; j++){
            graph[i][j] = 0;
        }
    }
    // 添加边
    graph[0][1] = 4; 
    graph[0][2] = 1; 
    graph[1][3] = 1; 
    graph[2][1] = 2; 
    graph[2][3] = 5; 
    graph[3][4] = 3; 
    graph[4][0] = 2; 
    graph[4][2] = 4;
  
    int src = 0;
    dijkstra(src);
 
    return 0;
}

这段代码实现了Dijkstra算法求解最短路径。该算法通过选取未访问节点中距离最近的节点来逐步扩展路径集合，最终找到从源节点到每个节点的最短路径，并输出到达每个节点的最短距离及路径。在代码中，我们使用邻接矩阵表示图，dist数组存储从源节点到每个节点的最短距离，visited数组表示节点是否已被访问，parent数组存储每个节点的父节点以构建路径。

### 回答3：
最短路径搜索是一个在图中寻找从一个起始节点到一个目标节点最短路径的问题。下面是一个简单的基于C语言的最短路径搜索代码：

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

#define INF 9999    // 表示无穷大

// 定义图的大小
#define VERTICES 6

// 使用邻接矩阵表示图
int graph[VERTICES][VERTICES] = {
    {0, 1, 3, INF, INF, INF},
    {1, 0, 2, 5, INF, INF},
    {3, 2, 0, 3, 1, 5},
    {INF, 5, 3, 0, 2, INF},
    {INF, INF, 1, 2, 0, 4},
    {INF, INF, 5, INF, 4, 0}
};

// 用于记录最小距离的数组
int dist[VERTICES];

// 记录节点是否被访问的数组
bool visited[VERTICES];

// 找到dist数组中的最小值
int minDistance() {
    int min = INF;
    int minIndex;

    for (int v = 0; v < VERTICES; v++) {
        if (!visited[v] && dist[v] <= min) {
            min = dist[v];
            minIndex = v;
        }
    }

    return minIndex;
}

// 实现最短路径搜索算法
void dijkstra(int start) {
    for (int i = 0; i < VERTICES; i++) {
        dist[i] = INF;
        visited[i] = false;
    }

    dist[start] = 0;

    for (int count = 0; count < VERTICES - 1; count++) {
        int u = minDistance();
        visited[u] = true;

        for (int v = 0; v < VERTICES; v++) {
            if (!visited[v] && graph[u][v] && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
}

// 打印最短路径
void printShortestPath(int destination) {
    printf("最短路径为：\n");
    for (int i = 0; i < VERTICES; i++) {
        if (i == destination) {
            printf("%d", dist[i]);
            break;
        }
    }
    printf("\n");
}

int main() {
    int start = 0;    // 起始节点
    int destination = 4;    // 目标节点

    dijkstra(start);
    printShortestPath(destination);

    return 0;
}

以上代码使用了Dijkstra算法来实现最短路径搜索。该算法使用邻接矩阵表示图，并使用dist数组记录最小距离。在主函数中，我们可以通过设置start和destination来定义起始节点和目标节点。运行代码后，将输出从起始节点到目标节点的最短路径长度。