求图（邻接矩阵存储）最短路径的狄克斯特拉算法

狄克斯特拉算法是一种求解图中最短路径的算法，它基于贪心策略，每次选择当前距离起点最近的节点作为中间节点，更新起点到其他节点的距离。在邻接矩阵存储的图中，可以使用一个一维数组dist来记录起点到每个节点的距离，另一个一维数组visited来记录每个节点是否已经被访问过。具体步骤如下：

1. 初始化dist数组，将起点到自身的距离设为，其他节点的距离设为无穷大（表示不可达）。

2. 初始化visited数组，将起点标记为已访问。

3. 对于起点相邻的节点，更新其距离dist值，将其标记为已访问。

4. 从未访问的节点中选择距离起点最近的节点作为中间节点，更新其相邻节点的dist值，将其标记为已访问。

5. 重复步骤4，直到所有节点都被访问过或者没有可达节点。

6. 最终dist数组中记录的就是起点到每个节点的最短距离。

需要注意的是，狄克斯特拉算法只适用于没有负权边的图，否则可能会出现无限循环的情况。如果图中存在负权边，可以使用Bellman-Ford算法来求解最短路径。

相关问题

用c语言构建有向带权图的邻接矩阵存储结构,使用狄克斯特拉算法求起始点到其余各点的最短路径。

好的，我可以为您介绍一下如何使用C语言构建有向带权图的邻接矩阵存储结构，以及使用Dijkstra算法求起始点到其余各点的最短路径。

先来介绍一下有向带权图的邻接矩阵存储结构。

邻接矩阵是一种常见的图的存储结构，使用一个二维矩阵来表示图中各个节点之间的关系。对于有向带权图，我们可以定义一个二维数组来表示其邻接矩阵，数组中的元素表示从一个节点到另一个节点的权值。

下面是一个示例代码：

#define MAXVEX 100        // 最大顶点数
#define INFINITY 65535    // 用65535来表示无穷大

typedef int EdgeType;     // 边的权值类型
typedef char VertexType;  // 顶点的数据类型

typedef struct {
    VertexType vexs[MAXVEX];       // 顶点表
    EdgeType arc[MAXVEX][MAXVEX];  // 邻接矩阵，存储边的权值
    int numVertexes, numEdges;     // 图中当前的顶点数和边数
} MGraph;

在上面的代码中，我们定义了一个结构体`MGraph`，其中包含了顶点表`vexs`、邻接矩阵`arc`、当前顶点数`numVertexes`和边数`numEdges`。`vexs`数组用来存储图中的顶点，`arc`矩阵用来存储边的权值。当两个节点之间没有边时，我们使用一个非常大的数来表示它们之间的距离，这里我们使用`INFINITY`来表示无穷大。

接下来是使用Dijkstra算法求起始点到其余各点的最短路径的示例代码：

void Dijkstra(MGraph G, int v0, int* dist, int* path)
{
    int i, j, k;
    int min;
    int final[MAXVEX];  // final[w]=1表示已经求得v0到vw的最短路径

    // 初始化
    for (i = 0; i < G.numVertexes; i++) {
        final[i] = 0;             // 顶点i未被处理
        dist[i] = G.arc[v0][i];   // 初始化v0到各个顶点的距离
        path[i] = -1;             // 初始化路径数组，-1表示无路径
    }

    final[v0] = 1;  // v0到自身的距离为0
    dist[v0] = 0;

    // 开始主循环，每次求得v0到某个顶点的最短路径
    for (i = 1; i < G.numVertexes; i++) {
        min = INFINITY;

        // 找到当前未处理顶点中距离v0最近的顶点k
        for (j = 0; j < G.numVertexes; j++) {
            if (final[j] == 0 && dist[j] < min) {
                min = dist[j];
                k = j;
            }
        }

        final[k] = 1;  // 标记顶点k已被处理

        // 更新当前最短路径及距离
        for (j = 0; j < G.numVertexes; j++) {
            if (final[j] == 0 && min + G.arc[k][j] < dist[j]) {
                dist[j] = min + G.arc[k][j];
                path[j] = k;
            }
        }
    }
}

在上面的代码中，我们定义了一个`Dijkstra`函数，它接收一个邻接矩阵图`G`、起始顶点`v0`、一个距离数组`dist`和一个路径数组`path`作为参数。`dist`数组用来存储起始顶点到各个顶点的距离，`path`数组用来存储最短路径中各个顶点的前驱节点。函数中的主循环会依次求出起始顶点到其余各个顶点的最短路径，每次处理一个顶点，直到所有顶点都被处理完。

希望这些代码能对您有所帮助！

用c语言构建有向带权图的邻接矩阵存储结构,使用狄克斯特拉算法求起始点到其余各点的最短路径。请给出完整代码

好的，以下是完整的 C 代码：

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

#define MAX_VERTICES 100
#define INF INT_MAX

typedef struct GraphType {
    int n;  // 정점의 개수
    int weight[MAX_VERTICES][MAX_VERTICES];  // 간선의 가중치
} GraphType;

int distance[MAX_VERTICES];  // 시작점으로부터의 최단거리
int found[MAX_VERTICES];  // 방문한 정점 표시

int choose(int distance[], int n, int found[]) {
    int i, min, minpos;
    min = INF;
    minpos = -1;
    for (i = 0; i < n; i++) {
        if (distance[i] < min && !found[i]) {
            min = distance[i];
            minpos = i;
        }
    }
    return minpos;
}

void shortest_path(GraphType* g, int start) {
    int i, u, w;
    for (i = 0; i < g->n; i++) {
        distance[i] = g->weight[start][i];
        found[i] = 0;
    }
    found[start] = 1;
    distance[start] = 0;

    for (i = 0; i < g->n - 1; i++) {
        u = choose(distance, g->n, found);
        found[u] = 1;
        for (w = 0; w < g->n; w++) {
            if (!found[w]) {
                if (distance[u] + g->weight[u][w] < distance[w]) {
                    distance[w] = distance[u] + g->weight[u][w];
                }
            }
        }
    }
}

int main(void) {
    GraphType g = { 7,
        {{ 0,  7, INF, INF,   3,  10, INF },
         { 7,  0,   4,  10,   2,   6, INF },
         {INF,  4,   0,   2, INF, INF, INF },
         {INF, 10,   2,   0,  11,   9,   4 },
         { 3,  2, INF,  11,   0, INF, INF },
         {10,  6, INF,   9, INF,   0, INF },
         {INF, INF, INF,   4, INF, INF,   0 } }
    };

    shortest_path(&g, 0);

    for (int i = 0; i < g.n; i++) {
        printf("0에서 %d까지의 최단거리: %d\n", i, distance[i]);
    }

    return 0;
}

这段代码实现了带权有向图的邻接矩阵存储结构和 Dijkstra 算法，可以计算起始点到其余各点的最短路径。