Dijkstra 算法写出单源最短路径问题的核心伪码

以下是Dijkstra算法的核心伪代码：

1. 初始化

   dist[s] = 0            //起点到起点的距离为0
   dist[v] = INF          //起点到其它顶点的距离为无穷大
   visited[s] = true      //起点已经访问过
   visited[v] = false     //其它顶点未访问过

2. 遍历

   while (还有未访问的顶点) {
       u = 未访问的顶点中距离起点最近的顶点
       visited[u] = true
       for (v 是 u 的邻接点) {
           if (visited[v] == false && dist[u] + weight(u, v) < dist[v]) {
               dist[v] = dist[u] + weight(u, v)
           }
       }
   }

其中，dist[i]表示起点s到顶点i的最短距离，visited[i]表示顶点i是否已经访问过，weight(u, v)表示边(u, v)的权值。算法的时间复杂度为O(n^2)，其中n为顶点数。如果使用堆优化，则时间复杂度可以优化为O(mlogn)，其中m为边数。

相关问题

Dijkstra算法，求解单源最短路径解法

Dijkstra算法是一种单源最短路径算法，用于计算图中一个节点到其他所有节点的最短路径。

具体实现步骤如下：

1. 创建一个数组dist，用于存储源点到图中各点的距离，初始时，将源点的距离设为0，其他点的距离设为正无穷。

2. 创建一个数组visited，用于存储各点是否已经访问过，初始时，将源点的visited值设为true，其他点的visited值设为false。

3. 对于源点的每个邻居，更新其距离dist值，如果新的距离比原来的距离小，则更新dist值。

4. 找到dist数组中未访问的最小值，将其对应的节点标记为visited。

5. 重复步骤3和4，直到所有点都被访问过，或者找不到更短的路径为止。

最终，dist数组中存储的就是源点到各点的最短距离。

Dijkstra算法的时间复杂度为O(n^2)，其中n为图中节点的个数。如果使用堆优化，可以将时间复杂度降为O(mlogn)，其中m为图中边的个数。

求用Dijkstra算法实现求单源最短路径的完整c语言代码

以下是使用Dijkstra算法实现求单源最短路径的完整C语言代码：

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

#define V 6 // 图中顶点数
#define INF INT_MAX // 表示两个顶点之间没有边

int graph[V][V] = { // 图的邻接矩阵表示法
    {0, 6, INF, 5, INF, INF},
    {INF, 0, 1, INF, INF, INF},
    {INF, INF, 0, INF, 3, INF},
    {INF, INF, INF, 0, INF, 9},
    {INF, INF, INF, INF, 0, INF},
    {INF, INF, INF, INF, INF, 0}
};

int dijkstra(int start, int end) {
    int dist[V], visited[V], minDist, minIndex, i, j;
    
    for (i = 0; i < V; i++) { // 初始化
        visited[i] = 0;
        dist[i] = graph[start][i];
    }
    
    visited[start] = 1; // 起点已访问
    
    for (i = 1; i < V; i++) {
        minDist = INF;
        for (j = 0; j < V; j++) { // 找出未访问过的距离最短的顶点
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                minIndex = j;
            }
        }
        visited[minIndex] = 1; // 将找到的顶点标记为已访问
        for (j = 0; j < V; j++) { // 更新距离
            if (!visited[j] && graph[minIndex][j] != INF && dist[minIndex] + graph[minIndex][j] < dist[j]) {
                dist[j] = dist[minIndex] + graph[minIndex][j];
            }
        }
    }
    
    return dist[end]; // 返回起点到终点的最短距离
}

int main() {
    int start = 0, end = 5;
    int shortestPath = dijkstra(start, end);
    printf("从%d到%d的最短距离为：%d\n", start, end, shortestPath);
    return 0;
}

注意，这里的图是一个有向带权图，采用邻接矩阵表示法。其中，`graph[i][j]`表示顶点i到j的边的权重。如果`graph[i][j]`的值为INF，表示顶点i和j之间没有边。在本代码中，我们假定起点为0，终点为5。在实际应用中，这些参数可以从外部输入。