Dijkstra算法主要是用来解决单源点最短路径问题。

该算法的思路如下：

• 在一个带非负权值的图G=(V,E)中，把顶点集V分为两组。
• S：已求出最短路径的顶点的集合，初始时集合S中只有源点s。
• V-S：尚未确定最短路径的顶点集合，将V-S中顶点按最短路径递增的次序加入S中。

function [mydistance,mypath]=mydijkstra(a,sb,db);
%输入：a——邻接矩阵；a(i,j)——i到j之间的距离，可以是有向的
%sb——起点的标号，db——终点的标号
%输出：mydistance——最短路的距离，mypath——最短路的路径

n=size(a,1);visited(1:0)=0;
distance(1:n)=inf;distance(sb)=0;	%起点到各顶点距离的初始化
visited(sb)=1;u=sb;		%u为最新的S集合顶点
parent(1:0)=0;		%前驱顶点的初始化
for i=1:n-1
	id=find(visited==0);	%查找V-S集合的顶点
	for v=id
		if a(u,v)+distance(u)<distance(v)
			distance(v)=distance(u)+a(u,v);		%修改标号值
			parent(v)=u;
		end
	end
	temp=distance;
	temp(visited==1)=inf;	%已标号点的距离换成无穷大
	[t,u]=min(temp);	%找标号值最小的顶点
	visited(u)=1;	%标记已经标号的顶点
end
mypath=[];
if parent(db)~=0 	%如果存在路！
	t=db;mypath=[db];
	while t~=sb
		P=parent(t);
		mypath=[P mypath];
		t=P;
	end
end
mydistance=distance(db);

源码链接: https://blog.csdn.net/qq_44394952/article/details/122587738.

1.课程设计要求

1）输入必要参数，包括：结点个数、节点间路径长度、给定节点；
2）输出给定节点到其它各节点的最短路径、径长；
3）节点间路径长度用矩阵形式表示；
4）可使用MATLAB 或者其他语言进行设计；
5）设计图形化界面展示本人的工作；

2.基本原理

1）Dijkstra算法是典型最短路径算法，用于计算单源点的最短路径问题，即求无向加权图G=<V,E,W>中一个节点到其他节点的最短路径。实际上就是根据网络的链路代价，采用广度优先搜索的思想，以起始点为中心向外层层扩展，直到扩展到终点为止来计算一对节点之间的最小代价路径。最短路径问题是图论中研究的一个重要课题，不仅仅指一般地理意义上的距离最短，还可以引申到其他的度量，如时间、费用、线路容量等。例如，城市交通中出行者选择出行路径，通信网络中的最可靠路径、最大容量路径问题等，都可以转化为最短路径问题。
2）操作步骤：
Step1：通过Dijkstra算法计算无向加权图G中的最短路径时，需要指定起点s。
Step2：引进两个集合S和U。S的作用是记录已求出最短路径的顶点以及相
应的最短路径长度，初始时被赋为 0。U记录还未求出最短路径的顶点
以及该顶点到起点s的距离，需要注意的是，U中顶点v的距离为(s,v)
的长度，如果s存在能直接到达v的边（s,v），则v的距离为（s, v）；
如果s不存在能直接到达v的边（s,v），则v的距离为∞。
Step3：初始时，S中只有起点s，U中是除s之外的顶点。
Step4：从U中找出路径最短的顶点k，并将其加入到S中；接着，从U中移
除顶点k并更新U中的顶点和顶点对应的路径，之所以更新U中顶点
的距离，是由于确定了k是求出最短路径的顶点，从而可以利用k来更
新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离，则(s,v)
的距离更新为(s,k)+(k,v)的距离
Step5：重复操作步骤4），直到遍历完所有结点。
Dijkstra 每次循环都可以确定一个顶点的最短路径，故程序需要循环 n-1 次。
3）图解举例：
以下图为例，以v0为起始结点，对Dijkstra进行算法原理演示


Step1：将v0放入集合S，从v0开始，
找到与其邻接的点：v1、v2、v3，更新D(v1)、D(v2)、D(v3)；
v0不与v4，v5，v6邻接，故D(v4)、D(v5)、D(v6)为∞。
在D(v)中找到最小值为1，其顶点为v1，
即此时已找到 v0到v1的最短路径为v0→v1。
Step2：将v1放入集合S，从v1开始，继续更新D(v)：
v1与v2不邻接，不更新；
v1与v3不邻接，不更新；
v1与v4不邻接，不更新；
v1与v5邻接，v0→v1→v5的路径为7比D(v5)=∞小，故更新D(v5) ；
v1与v6不邻接，不更新。
在D(v)中找到最小值为2，其顶点为v2，
即此时又找到v0到v2的最短路径为v0→v2。
Step3：将v2放入集合S，从v2开始，继续更新D(v)：
v2与v3不邻接，不更新；
v2与v4邻接，v0→v2→v4的路径为7比D(v4)=∞小，故更新D(v4) ；
v2与v5邻接，v0→v2→v5的路径为6比D(v5)=7小，故更新D(v5) ；
v2与v6不邻接，不更新；
在D(v)中找到最小值为3，其顶点为v3，
即此时又找到v0到v3的最短路径为v0→v3。
Step4：将v3放入集合S，从v3开始，继续更新D(v)：
v3与v4邻接，v0→v3→v4的路径为7等于D(v4)=7，故不更新；
v3与v5不邻接，不更新；
v3与v6不邻接，不更新；
在D(v)中找到最小值为6，其顶点为v5，
即此时又找到v0到v5的最短路径为v0→v2→v5。
Step5：将v5放入集合S，从v5开始，继续更新D(v)：
v5与v4不邻接，不更新；
v5与v6邻接，v0→v2→v5→v6的路径为14比D(v6)=∞小，故更新D(v6) ；
在D(v)中找到最小值为7，其顶点为v4，
即此时又找到v0到v4的最短路径为v0→v2→v4。
Step6：将v4放入集合S，从v4开始，继续更新D(v)：
V4与v6邻接，v0→v2→v4→v6的路径为14等于D(v6)=14，故不更新；
在D(v)中找到最小值为14，其顶点为v6，
即此时又找到v0到v6的最短路径为v0→v2→v4→v6。
Step7：将v6放入集合S，所有点都已找到，停止。

3.仿真程序代码及分析

链接: https://blog.csdn.net/qq_44394952/article/details/122587738.

4.仿真结果及分析

输入结点数量、路径数量并依次输入每两个相连结点及其之间的路径长度：

输出结点间路径长度的矩阵

功能1：输入起始结点和目的结点，输出路径和距离

功能2：输出以v0为起始结点，其余各点为目的结点的全部路径和距离
通过测试发现c语言编程实现的结果与计算结果一致。
综上，通过c语言编程主要实现了两个功能：一是输入起始结点和目的结点，输出路径和距离；二是输出以v0为起始结点，其余各结点为目的结点的全部路径和距离。同时，c语言编程实现的实现因为可以输入结点数量、路径数量及每两个相连结点及其之间的路径长度，从而更具有普适性，不限制于某一给定的无向加权图。

Dijkstra算法：
问题：给定一个带权图G=(V,E,w),找到从给定源点u0到其他各点的最短路径。
Step:
求带权图G(V,E)的点v0到其他各点的最短路径；
1.初始时，S={v0},U={v1,v1…vn};点v0到其他点的最短距离为<v0,vi>(i=1,2,3…n)的权；将v0到其他各点vi的最短路径中vi的前驱动点初始化为v0;
2,从U中选取u，使得当前v0到u的最短路径的距离小于v0到U中其他各点的最短路径的距离，将u加入S,并将u从U中删除
3,遍历每个在U中的点s，如果以u为中介点的最短路径的距离小于当前存储的距离，更新从v0到s的最短路径的距离，并将v0到s的最短路径的s的前驱动点更新为u;
4,重复2,3直到U为空；

绿色顶点表示源点到该顶点的距离已确定 蓝色顶点表示要加入集合S的顶点 {dis,v},v表示前驱动点，dis表示源点到该顶点的最短距离

代码：

#include <stdio.h>
#define INF 10000000
#define MaxSize 50
int graph[MaxSize][MaxSize];  //MaxSize为最大顶点数
int dis[MaxSize];             //dis[i]为源点到顶点i的最短距离
int visit[MaxSize];            //visit[i]标记顶点i的最短路径是否已求出visit[i] == 1表示已求出
int prevetrix[MaxSize];       //前驱动点
void dij(int n)
{    
    int count = 0;          //count是已求出最短路径的顶点数目
    visit[0] = 1;    
    prevetrix[0] = 0;    
    count++;    
    for (int i = 1; i < n; i++)    //初始化
    {        
        dis[i] = graph[0][i];        
        prevetrix[i] = 0;    
    }    
    while (count < n)    
    {        
        int min = INF, target_index;        
        for (int i = 1; i < n; i++)        
        {            
            if (visit[i] == 0 && min > dis[i])         //找到距离源点最短的顶点target_index
            {                
                min = dis[i];                
                target_index = i;            
            }        
        }        
        visit[target_index] = 1;        
        count++;        
        for (int i = 1; i < n; i++)        
        {            
            if (visit[i] == 0 && dis[target_index] + 
            graph[target_index][i] < dis[i])            //更新
            {                
                dis[i] = dis[target_index] + graph[target_index][i];
                prevetrix[i] = target_index;            
            }        
        }    
    }
}
int main()
{    
    int n, m;    
    scanf("%d %d", &n, &m);    //n为顶点数,m为边数
    int a, b, w, path[n];    
    for (int i = 0; i < n; i++)    
    {        
        for (int j = 0; j < n; j++)        
        {            
            graph[i][j] = INF;        
        }    
    }    
    for (int i = 0; i < m; i++)    
    {        
        scanf("%d %d %d", &a, &b, &w);        //a为起始点,b为终点,w为边a->b的权重
        graph[a][b] = w;    
    }     
    dij(n);    
    printf("\n\n");    
    for (int i = 1; i < n; i++)    
    {        
        if (dis[i] == INF)        
        {            
            printf("顶点0到顶点%d没有最短路径\n", i);        
        }        
        else        
        {            
    	    printf("顶点0到顶点%d有长为%d的最短路径：", i,dis[i]);            
    	    int cur = i, index = 0;            
            path[index] = cur;            
            while (1)            
            {                
                path[index + 1] = prevetrix[path[index]];                
                if (path[index + 1] == 0)                    
                    break;                
                index++;            
            }            
            for (int j = index + 1; j > 0; j--)            
            {                
                printf("%d->", path[j]);            
            }            
            printf("%d\n", path[0]);        
        }    
    }
}

输入：
6 8
0 2 10
0 4 30
0 5 100
1 2 5
2 3 50
3 5 10
4 5 60
4 3 20
输出：
顶点0到顶点1没有最短路径
顶点0到顶点2有长为10的最短路径：0->2
顶点0到顶点3有长为50的最短路径：0->4->3
顶点0到顶点4有长为30的最短路径：0->4
顶点0到顶点5有长为60的最短路径：0->4->3->5

注意：diskstra算法只能求边权值为非负值的情况