dijkstra算法求最短路径c语言

### 回答1：
Dijkstra算法是一种用于求解图中最短路径的算法，它是以荷兰计算机科学家Edsger W. Dijkstra的名字命名的。该算法的基本思想是从起点开始，逐步扩展到其他节点，直到到达终点为止。在扩展的过程中，每个节点都会记录到达它的最短路径和距离，直到所有节点都被扩展为止。

在C语言中，可以使用邻接矩阵或邻接表来表示图，然后使用Dijkstra算法来求解最短路径。以下是一个简单的C语言实现：

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

#define V 6 // 图的顶点数

int minDistance(int dist[], int sptSet[]) {
    int min = INT_MAX, min_index;
    for (int v = ; v < V; v++) {
        if (sptSet[v] ==  && dist[v] <= min) {
            min = dist[v];
            min_index = v;
        }
    }
    return min_index;
}

void printSolution(int dist[]) {
    printf("Vertex \t Distance from Source\n");
    for (int i = ; i < V; i++) {
        printf("%d \t %d\n", i, dist[i]);
    }
}

void dijkstra(int graph[V][V], int src) {
    int dist[V];
    int sptSet[V];

    for (int i = ; i < V; i++) {
        dist[i] = INT_MAX;
        sptSet[i] = ;
    }

    dist[src] = ;

    for (int count = ; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = 1;

        for (int v = ; v < V; v++) {
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    printSolution(dist);
}

int main() {
    int graph[V][V] = {
        {, 2, 4, , , },
        {2, , 1, 4, 2, },
        {4, 1, , , 3, },
        {, 4, , , 3, 2},
        {, 2, 3, 3, , 2},
        {, , , 2, 2, }
    };

    dijkstra(graph, );

    return ;
}

在这个例子中，我们使用邻接矩阵来表示图，其中表示两个节点之间没有边，其他数字表示边的权重。我们从节点开始，使用Dijkstra算法来计算到其他节点的最短路径。最后，我们输出每个节点到起点的最短距离。

### 回答2：
Dijkstra算法是一种计算图中最短路径的常用算法。Dijkstra算法可以处理图中带权的有向图或者无向图，但是，我们需要要求所有的边的权值都是非负数。算法会从起始点开始，计算起始点到所有节点的最短路径，并把所有的最短路径存储在一个数组中。我们可以用C语言来实现Dijkstra算法，下面我们来讲解一下具体的实现细节。

我们假设输入的图用一个矩阵来表示，用二维数组graph来存储，这里我使用10*10的二维数组。其中graph[i][j]代表节点i到节点j的边的权值，若i到j的边不存在，则graph[i][j]为0。同时我们需要定义一个数组distance，用来存储起始点到各个点的最短距离。还需要定义一个数组visited，用来判断每个点是否被遍历过。

我们从起始点开始，将起始点的visited设置为1，并将起始点到各个点的距离初始化为graph[0]。然后我们开始遍历所有的点，找到当前距离起始点最近的点。我们将这个点设置为visited，并更新其它节点的距离。

C语言实现Dijkstra算法的代码如下：

#include <stdio.h>
#define INF 0x3f3f3f3f // 表示无限大

void dijkstra(int graph[10][10], int start) { // 传入图的矩阵和起始点
    int distance[10]; // 存储起始点到所有点的距离
    int visited[10]; // 标记每个点是否被访问过

    // 初始化数组
    for(int i = 0; i < 10; i++) {
        distance[i] = graph[start][i]; // 起始点到各个点的距离
        visited[i] = 0; // 未访问过
    }

    visited[start] = 1; // 起始点已访问

    // 遍历所有点
    for(int i = 0; i < 10; i++) {
        int min_distance = INF; // 最近的距离
        int min_index; // 最近的点的下标

        // 找到当前距离起始点最短的点
        for(int j = 0; j < 10; j++) {
            if(visited[j] == 0 && distance[j] < min_distance) {
                min_distance = distance[j];
                min_index = j;
            }
        }

        visited[min_index] = 1; // 标记点已访问

        // 更新距离
        for(int j = 0; j < 10; j++) {
            if(visited[j] == 0 && distance[j] > distance[min_index] + graph[min_index][j]) {
                distance[j] = distance[min_index] + graph[min_index][j];
            }
        }

        // 输出当前点到起始点的最短距离
        printf("Point %d distance from start: %d\n", min_index, distance[min_index]);
    }
}

int main() {
    // 初始化图的矩阵
    int graph[10][10] = {
        {0, 1, 3, 0, 0, 0, 0, 0, 0, 0},
        {1, 0, 0, 2, 6, 0, 0, 0, 0, 0},
        {3, 0, 0, 4, 0, 1, 0, 0, 0, 0},
        {0, 2, 4, 0, 0, 0, 2, 5, 0, 0},
        {0, 6, 0, 0, 0, 0, 6, 0, 3, 0},
        {0, 0, 1, 0, 0, 0, 0, 5, 0, 3},
        {0, 0, 0, 2, 6, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 5, 0, 0, 0, 2},
        {0, 0, 0, 0, 3, 0, 0, 0, 0, 4},
        {0, 0, 0, 0, 0, 3 ,0, 2, 4, 0}
    };

    dijkstra(graph, 0); // 从起始点0开始求最短路径

    return 0;
}

以上就是Dijkstra算法在C语言中的实现，当然这只是简单的实现，如果需要优化效率，我们还可以使用堆来优化算法。

### 回答3：
Dijkstra算法是一种用于寻找图形中单个源点到其他所有节点的最短路径的算法。它是一种贪心算法，通过构建阶段性的最短路径树来逐步扩展源节点到其他节点的最短路径。这个算法已经成为了许多网络路径规划和路由算法的基础。

下面是用c语言实现Dijkstra算法求最短路径的示例代码：

#include <limits.h> 
#include <stdio.h> 
#define V 9 

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 printSolution(int dist[]) 
{ 
    printf("Vertex \t Distance from Source\n"); 
    for (int i = 0; i < V; i++) 
        printf("%d \t\t %d\n", i, dist[i]); 
} 
  
void dijkstra(int graph[V][V], int src) 
{ 
    int dist[V]; 
  
    bool sptSet[V]; 
  
    for (int i = 0; i < V; i++) 
        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]) 
                dist[v] = dist[u] + graph[u][v]; 
    } 
  
    printSolution(dist); 
} 
  
int main() 
{ 
    int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 }, 
                        { 4, 0, 8, 0, 0, 0, 0, 11, 0 }, 
                        { 0, 8, 0, 7, 0, 4, 0, 0, 2 }, 
                        { 0, 0, 7, 0, 9, 14, 0, 0, 0 }, 
                        { 0, 0, 0, 9, 0, 10, 0, 0, 0 }, 
                        { 0, 0, 4, 14, 10, 0, 2, 0, 0 }, 
                        { 0, 0, 0, 0, 0, 2, 0, 1, 6 }, 
                        { 8, 11, 0, 0, 0, 0, 1, 0, 7 }, 
                        { 0, 0, 2, 0, 0, 0, 6, 7, 0 } }; 
  
    dijkstra(graph, 0); 
  
    return 0; 
} 

这个示例代码实现了一个最短路径算法，可以根据自己输入的要求，生成对应的路径长度值和点集，从而求出图形中单个源点到其他所有节点的最短路径。