c语言写邻接矩阵的最短路径的Dijkstra算法（附有详细代码）-Toy模板网

这篇具有很好参考价值的文章主要介绍了c语言写邻接矩阵的最短路径的Dijkstra算法（附有详细代码）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

c语言写邻接矩阵的最短路径的Dijkstra算法（附有详细代码）

(1) 用dis数组来存储源点1到其他顶点的初始路径，标记1号顶点，

此时dis数组中的值称为最短路径的估计值。

(2) 从dis数组中找出离源起点最近的点2号，以2号顶点为源点进行找最近的顶点。把2号顶点标记，表示已经有最小值。

以2号顶点为源点，看2号顶点有哪些出边，看能不能优化，再短一些 2->3：9，2->4：3 而dis中最短路径的估计值，1->2：1, 1->3：12 那么结合一下 1->2->3：1+9=10，比1->3：12 小， 1->2：1 和 2->4：3，那么1->2->4：4 所以要更新 dis中的最短路径估计值，

c语言写邻接矩阵的最短路径的Dijkstra算法（附有详细代码）

(3) 此时1号和2号顶点已经标记，表示已经最小值，现在在3号和4号找，4号顶点距离源点最近，所以以4号顶点进行找，标记4号顶点

4号的出边： 4->3：4，4->5：13，4->6：15。用刚才的方法进行更新估计值。 1->3:10 比 1->4->3：4+4=8，大，所以更新 1->4：4，4->5：13+4=17，更新。 1->4：4，4->6：15+4 = 19。更新

c语言写邻接矩阵的最短路径的Dijkstra算法（附有详细代码）

(4)从3号，5号，6号，找最短路径8，标记3号顶点。以相同的方法进行更新。

c语言写邻接矩阵的最短路径的Dijkstra算法（附有详细代码）

(5)从5号和6号顶点查找，标记5号。以相同的方法进行更新。

c语言写邻接矩阵的最短路径的Dijkstra算法（附有详细代码）

(6)此时剩余6号顶点，6号的出边没有，此时所有的顶点都以遍历完，dis中的值就是最终的结果。

c语言写邻接矩阵的最短路径的Dijkstra算法（附有详细代码）

测试说明

平台会对你编写的代码进行测试：下面的测试用图见上面的图片中的图。请注意，上图中节点编号从1开始，因此在代码书写中可以选择浪费一部分数组空间（即浪费数组下标为0的空间），也可以选择不浪费数组中下标为0的空间，而在代码中对编号进行对应计算处理。测试输入（前面9行都是构造图需要的起点终点权值，最后一行的三个数分别是图结构输入结束符0、须计算的路径的起点和终点）：

1 2 1

1 3 12

2 3 9

2 4 3

4 3 4

4 5 13

3 5 5

4 6 15

5 6 4

0 1 6

预期输出（输出的是1号点到6号点的最短路径长度）： 17

#include <stdio.h>
#include <stdlib.h>
#include<iostream>
using namespace std;
#define N  250//至多有6个顶点
#define MAX  32767;//定义的无穷
//#define V  0//源点
int V,S;

//邻接矩阵数据结构 
typedef  struct {
    int vcount;//顶点数
    int  arcs[N][N]; //带权关系矩阵
} GraphMatrix;

GraphMatrix* initGraphMatrix()//完成图初始化-邻接矩阵
{
    GraphMatrix* G;
    G = (GraphMatrix*)malloc(sizeof(GraphMatrix));
    int  v, s;//输入顶点个数和边的个数
    //scanf("%d %d", &v, &s);
    v = 6, s = 9;
    G->vcount = v;

    int i, j;
    for (i = 0; i <= G->vcount; i++) {
        for (j = 0; j <= G->vcount; j++) {
            G->arcs[i][j] = MAX;
        }
    }//初始化矩阵

    int start, end,quan;//起点，终点，权值

    scanf("%d %d %d", &start, &end, &quan);
    while (start != 0) {
        G->arcs[start - 1][end - 1] = quan;
        scanf("%d %d %d", &start, &end, &quan);
    }
    V = end-1;
    S = quan - 1;
    return G;
}

void Dijkstra_quan(GraphMatrix* G) {
    int s[N];//判断点是否访问过
    int dist[N];//存储最短路径
    for (int i = 0; i < G->vcount; i++)
    {
        dist[i] = G->arcs[V][i];
        s[i] = 0;
    }//先把源点到各个点距离赋值dist,并且每个点都未访问
    s[V] = 1;//源点已经访问
    int minv = -1;//在dist中查找未访问过的点的最小值的点
    int minquan = 100;//前一次的最小权值
    for (int i = 1; i < G->vcount; i++)//s中已有一个点表示访问过，所以要从1开始
    {
        for (int j = 0; j < G->vcount; j++)
        {
            if (!s[j] && dist[j] < minquan)
            {
                minv = j;
                minquan = dist[j];
            }
        }//寻找dist中为访问过点的最小值的点
        s[minv] = 1;
        for (int j = 0; j < G->vcount; j++)
        {
            if (s[j] != 1 && dist[j] > minquan + G->arcs[minv][j])
            {
                dist[j] = minquan + G->arcs[minv][j];
            }
        }
        minquan = 1000;
    }
    for (int i = 0; i < G->vcount; i++) {
        if (i==S) {
            cout << dist[i];
        }
    }
}


int main() {
    GraphMatrix* G = initGraphMatrix();
    Dijkstra_quan(G);

    return 0;
}

文章来源地址https://www.toymoban.com/news/detail-451715.html

到了这里，关于c语言写邻接矩阵的最短路径的Dijkstra算法（附有详细代码）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！