dijkstra最短路径算法代码（dijkstra算法能得出最短路径的最优解）

今天给各位分享dijkstra最短路径算法代码的知识，其中也会对dijkstra算法能得出最短路径的最优解进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

本文目录一览：

• 1、图遍历算法之最短路径Dijkstra算法
• 2、寻找最短路径的汇编语言实现源代码是什么(用Dijkstra 算法)
• 3、最短路径的Dijkstra算法
• 4、用dijkstra算法解决最短路径问题c语言代码实现时怎样将每一个路径的顶点次序依次输出出来？
• 5、用Dijkstra算法求最短路径的MATLAB程序
• 6、关于最短路的Dijkstra算法的程序源代码!

图遍历算法之最短路径Dijkstra算法

最短路径问题是图论研究中一个经典算法问题，旨在寻找图中两节点或单个节点到其他节点之间的最短路径。根据问题的不同，算法的具体形式包括：

常用的最短路径算法包括：Dijkstra算法，A 算法，Bellman-Ford算法，SPFA算法（Bellman-Ford算法的改进版本），Floyd-Warshall算法，Johnson算法以及Bi-direction BFS算法。本文将重点介绍Dijkstra算法的原理以及实现。

Dijkstra算法，翻译作戴克斯特拉算法或迪杰斯特拉算法，于1956年由荷兰计算机科学家艾兹赫尔.戴克斯特拉提出，用于解决赋权有向图的 单源最短路径问题 。所谓单源最短路径问题是指确定起点，寻找该节点到图中任意节点的最短路径，算法可用于寻找两个城市中的最短路径或是解决著名的旅行商问题。

问题描述 ：在无向图 中， 为图节点的集合， 为节点之间连线边的集合。假设每条边 的权重为 ，找到由顶点 到其余各个节点的最短路径（单源最短路径）。

为带权无向图，图中顶点 分为两组，第一组为已求出最短路径的顶点集合（用 表示）。初始时 只有源点，当求得一条最短路径时，便将新增顶点添加进 ，直到所有顶点加入 中，算法结束。第二组为未确定最短路径顶点集合（用 表示），随着 中顶点增加， 中顶点逐渐减少。

以下图为例，对Dijkstra算法的工作流程进行演示（以顶点 为起点）：

注：

01） 是已计算出最短路径的顶点集合；

02） 是未计算出最短路径的顶点集合；

03） 表示顶点 到顶点 的最短距离为3

第1步 ：选取顶点 添加进

第2步 ：选取顶点 添加进 ，更新 中顶点最短距离

第3步 ：选取顶点 添加进 ，更新 中顶点最短距离

第4步 ：选取顶点 添加进 ，更新 中顶点最短距离

第5步 ：选取顶点 添加进 ，更新 中顶点最短距离

第6步 ：选取顶点 添加进 ，更新 中顶点最短距离

第7步 ：选取顶点 添加进 ，更新 中顶点最短距离

示例：node编号1-7分别代表A,B,C,D,E,F,G

(s.paths - shortest.paths(g, algorithm = "dijkstra"))输出结果：

(s.paths - shortest.paths(g,4, algorithm = "dijkstra"))输出结果：

示例：

找到D（4）到G（7）的最短路径：

[1] 维基百科，最短路径问题： ；

[2]CSDN，Dijkstra算法原理： ;

[3]RDocumentation: ;

[4]RDocumentation: ;

[5]Pypi:

寻找最短路径的汇编语言实现源代码是什么(用Dijkstra 算法)

Dijkstra算法Dijkstra算法是典型的最短路径算法，用于计算一个节点的最短路径中的所有其他节点。其主要特点是出发点为中心向外层层扩展，直到扩展到结束日期。 Dijkstra最短路径算法能得出最佳的解决方案，但许多节点，它遍历计算，这样的效率是低的。最短路径算法的

Dijkstra算法是非常有代表性的许多专业课程的基本内容进行了详细的介绍，如数据结构，图论，运筹学，等等。

Dijkstra算法的一般性发言一般有两种方式，永久和临时的标签，开启，关闭表的方式之一，德鲁表示，为了引进和下面的A *算法和D *算法一致，这里是开放的，关闭表。

贪婪的方法，算法策略

大概过程如下：

创建两个表，打开，关闭。

OPEN表保存没有调查之前已产生的所有节点，CLOSED表中记录已访问过的节点。

1。的道路网络的出发点和等待在公开组的检查没有检查点，此点。

2。打开表，以找出从起点最近的点，以确定所有的子节点，这一点，这点上关闭表。

3。遍历访问这个点的子节点。获得这些子节点从子节点到OPEN表的放电的开始点的距离的值。

4。重复步骤2和步骤3，直到OPEN表为空，或找到目标点。

[编辑本段]算法是

包括的文件

定义MAXNUM 765432100的

使用命名空间std;

ifstream的散热片（Dijkstra算法。在“）;

ofstream这样的FOUT（”Dijkstra.out“）;

诠释地图[501] [501];

布尔is_arrived [501];

诠释区[501] [501]，堆栈[501];

整数P，Q，K，路径，源代码，顶点，温度，SetCard

诠释FindMin（）

{

诠释P，温度= 0，MINM = MAXNUM;

（P = 1，P =顶点，P + +）

（（区[P] MINM）（！is_arrived [P] ））

{

MINM区[P]。

温度= P;

}

收益温度;

}

：（ ）

{

的memset（is_arrived，0，大小（is_arrived））;

鳍源代码顶点;

（P = 1，P =顶点，P + +）

（Q = 1，Q =顶点，Q + +）

{

鳍地图[P] [Q];

（图[ P] [Q] == 0）地图[P] [Q] = MAXNUM;

}

为（P = 1，P =顶点，P + +）

{ /区[P] =地图[来源] [P];

（区[P]！= MAXNUM）

[P] =源;

其他

[P] = P;

}

is_arrived [来源] = TRUE;

SetCard = 1;

{

温度= FindMin（）;

（Temp! = 0）

{

SetCard SetCard +1;

is_arrived [温度] = TRUE;

（P = 1，P =顶点，P + +）

（（区[P]区[温度] +地图[温度] [P]）（！is_arrived [P]））

{

区[P] =区[温度] +地图[温度] [P]

[P] =温度;

}

}

其他

突破; BR /}

（SetCard! =顶点）;

（P = 1，P =顶点，P + +）

（p! =源）

{

FOUT “======================== \ n”;

FOUT “来源：”; 资料来源“\ n目标：”“P '\ n';

（区[P] == MAXNUM）

{

FOUT ”距离：“ “无限\ n”;

FOUT “路径：没办法！”;

}

其他

{

FOUT“距离”：“区[P] '\ n';

K = 1;

路径= P;

同时（从[路径]！=路径）

{

栈[K] =路径;

路径=从[路径];

K = K +1;

}

FOUT “路径：”（Q = K-1，Q = 1，Q - ）

FOUT“ - ”栈[问];

}

FOUT “\ ?======================== \ n \ n“;}

fin.close（）;

fout.close（）;

返回0;

}

样品输入

2

7

00 20 50 30 00 00 00

20 00 25 00 00 70 00

50 25 00 40 25 50 00

30 00 40 0??0 55 00 00

00 00 25 55 00 10 00

00 70 50 00 10 00 00

00 00 00 00 00 00 00

样本输出

========================

来源：2

目标：1

距离：20

路径：2 - 1

==================== ====

========================

来源：

目标：3

距离：25

路径：2 - 3 ========================

===== ===================

来源：

目标：4

距离：50

路径：2 - 1 - ======================== 4

============== =========

来源：

目标：5

距离：50

路径：2 - 3 - 5

== ======================

========================

来源：

目标：6

距离：60

路径：2 - 3 - 5 - 6

========= ===============

========================

来源：2

目标：7

距离：无限

路径：没办法！

========================

示例程序和相关子程序如下：

无效的Dijkstra（INT N，INT [ ]距离的int [] iPath标）

{

诠释最短距离，U

INT I，J;

/ /从n个顶点的邻接矩阵的副本可以摆脱行了，是复制前n行的距离[]

（i = 0;我VerNum，我+ +）

{

距离=圆弧[N];

访问= 0;

} / / n个结点访问，因为n个顶点的出发点是

访问[N] = 1;

/ /找到的顶点其他顶点的路线，并且它不是顶点n的开头，没有先前旅游。

/ /相当于u点，这一点是没有的出发点N（i = 0; I VerNum，我+ +）

{

U = 0

最短距离=否;

为（J = 0; VerNum; + +）

（访问[J] == 0 （距离[J]最短距离））

{

最短距离=距离[J];

ü= J;

}

/ /例如P1871图G6距离=无，无，无，30,100]第一次看的是V2，U = 2

/ /找到结束，的MinDis意味着它无法连接，然后返回。这种情况是相似的V5。

（最短距离==否）返回;

/ /建立一个u个顶点将被用于顶点u，相当于弧[V，U +弧U，W] 。

访问[U] = 1;

/ /找到一个U顶点到所有其他顶点最小的路径实际上是在寻找弧] [U，J，J值在[0， VerNum]。

/ /如果是圆弧，U [I] +凯旋门[U，J] ARC [I，J]，ARC [I，J] =弧[I，U] +凯旋门[U J] 弧[I，J]

/ /的做法，因为距离[]是期望的结果，起始点确定的情况下，那就是：

/ /如果（距离[U] +圆弧[U，J）=距离[J]：

/ /距离[J]距离[U] + [U，J弧];

/ /保存iPath标[] u点数量;

/ /同样，设置访问量：新发现的路由[J] = 0，经过寻找另一条道路，这条道路可能不利用。 V3

（J = 0; VerNum; + +）

（访问[J] == 0 弧U，J] U！= J） / {

（（距离[U] +圆弧[U，J）=距离[J]）

{

距离[J]距离[U] +弧[ U，J];

访问[J] = 0;

iPath标[J] = U;

}

}

}

} / /辅助功能

无效的Prim（），

{

INT I，M，N = 0;

为（i = 0;我VerNum;我+ +）

{

访问= 0;

T =新的TreeNode（）;

T.Text = V;

}

访问[N] + +;

listBox1.Items。添加（V [N]）;

（参观（） 0）

{

（（M = MinAdjNode（N））！= -1）

{ BR / T [N]。 Nodes.Add（T [M]）;

N = M;

访问[N] + +;

}

其他

{

?= MinNode（0）;

（N 0）T [旻]。 Nodes.Add（T [敏]）;

访问[N] + +;

}

listBox1.Items.Add（V [N]）;

} treeView1.Nodes.Add（T [0]）;

}

的无效TopoSort（）

{

INT I，N;

listBox1.Items.Clear（ ）;

栈S =新的堆栈（）;

为（i = 0;我VerNum，我+ +）

访问= 0;

为（= VerNum- 1 = 0; I - ）

（入度（I）== 0）

{

S.Push（I）;

访问+ +; ...... /}

而（S.Count！= 0）

{

N =（INT）S.Pop（）;

listBox1.Items.Add（V [N] ）;

CLEARLINK（N）;

为（i = VerNum-1 = 0; I - ）

（分== 0 入度（I）== 0）

{

S.Push（I）;

访问+ +;

}

}

}

无效AOETrave（INT N，树节点TR，W）

{

INT I，W0;

（出度（N）== 0）返回;

（i = 0; VerNum; + +）

（（W0 =圆弧[N，I]）！= 0）

{

listBox1.Items.Add（V +“\ t”+（W + W0）的ToString（）+“\ t”+ i.ToString（）+“\ t”+ n.ToString（））;

TreeNode的T1 =新的TreeNode（）;

T1.Text = V + “W =”+（W + W0）。的ToString（）+“]”;

TR.Nodes.Add（T1）;

AOETrave（I，T1，W + W0）;

}

}

无效AOE（）

{

INT I，W = 0，M = 1;

TreeNode的T1 =新的TreeNode（）;

为（i = 0; VerNum;我+ +）

{

访问= 0;

}

T1.Text = V [0];

listBox1.Items.Add（“父母符号显示生成树：“）;

listBox1.Items.Add（”V \ TW \工业贸易署\ TPID“）;

为（i = 0;我VerNum，我+ +）

{

（（W =弧[0，I]）！= 0）

{

listBox1.Items.Add（V +“\ t”+ w.ToString（）+“\ T“+ i.ToString（）+”\ T0“）;

TreeNode的T2 =新的TreeNode（）;

T2.Text = V +”W =“+ w.ToString（）+” “;

AOETrave（I，T2，W）;

listBox1.Items.Add（”\ t \ t树“+ m.ToString

T1.Nodes.Add（ T2），（））;

米+ +;

}

}

treeView1.Nodes.Clear（）;

treeView1.Nodes.Add（T1）;

}

IsZero（）

{

我;

为（i = 0;我VerNum，我+ +）

（LineIsZero （一） = 0）返回;

返回-1;

}

诠释LineIsZero（N）

{

我

（i = 0; VerNum;我+ +）

（电弧[N，I] = 0）返回;

返回-1;}

：无效DepthTraverse（）

{

INT I，M;

（i = 0; VerNum，我+ +）

{

访问= 0; BR / T =新的TreeNode（）;

T.Text = V

R = 0;

}

而（（M = IsZero（）） = 0）

{

（访问[M] == 0）

{

listBox1.Items.Add（V [M]）;

R [M] = 1 ;}

访问[M] + +;

DTrave（M）;

}

为（i = 0; {

（R == 1）

treeView1.Nodes.Add（T）;

}

}

无效DTrave（N） / {

我;

（LineIsZero（N）0）返回;

为（i = VerNum-1 = 0; I - ）

（弧[N] = 0）

{

弧[N，I] = 0;

弧[I，N] = 0;

（访问= = 0）

{

listBox1.Items.Add（V）;

T [N]。 Nodes.Add（T）;

R = 0;

}

访问+ +;

DTrave（I）;

}

} ：无效BreadthTraverse（）

{

INT I，M;

（i = 0; VerNum，我+ +）

{

访问= 0;

T =新的TreeNode（）;

T.Text = V;

R = 0;

}

而（（M = IsZero（）） = 0 ）

{

（访问[M] == 0）

{

listBox1.Items。添加（V [M]）;

R [M] = 1;

}

访问[M] + +;

BTrave（M）;

} BR /（i = 0;我VerNum，我+ +）

{

（R == 1）

treeView1.Nodes.Add（T）;

}

}

无效BTrave（N）

{

我

队列Q =新的Queue（）;

Q.Enqueue（N）

而（Q.Count！= 0）

{

为（i = 0;我VerNum，我+ +）

{

（电弧N，I] = 0）

{

弧[N，I] = 0;

弧[N] = 0;

（访问== 0）

{

listBox1.Items.Add（V）;

T [N]。 Nodes.Add（T）;

直径= 0;

}

访问+ +;

Q.Enqueue（I）;

}

} BR / N =（int）的Q.Dequeue（）;

}

}

诠释MinNode（VN）

{

INT I，J，N，米，最小=否;

N = -1，M = -1;

为（i = VN我VerNum，我+ +）

中for（j = 0; J VerNum; + +）

（电弧[I，J] = 弧[I，J]闵分== 0 访问[J] == 1）

{ BR /最小值=弧[I，J]; N = I，M = J;

}

敏=旻= M

返回n;

} BR /诠释MinAdjNode（N）

{

我，敏，米;

最小值=否，M = -1;

（i = 0; I VerNum，我+ +）

（电弧[N，I] =没有访问 == 0 最小弧[N，I] 访问[N] == 1）{BR / BR /最小值=弧[N，I]，M = I;}

返回米;

}

INT访问（）

{

INT I，S = 0;

为（i = 0; VerNum，我+ +）

（访问== 0）+ +;

返回s;

}

[编辑本段] Dijkstra算法的Pascal实现：

程序Dijkstra的;

VAR

答：ARRAY [1 .. 100,1 .. 100的整数;

标志：数组[1] .. 100]布尔值;

W，X，N，I，J，分，明尼苏达州：整数;

开始

readln（N）;

我：= 1到n

开始

对于j = 1到n

读（A）;

readln;

结束;

fillchar（标志中，sizeof（标志），假）;

标志[1]：= TRUE;

明尼苏达州：= 1;

为：= 2到n

开始

分： 32767;

W：=明尼苏达州

我：= 1到n做

（W ）和（[W，I] MIN），然后

开始

分：= [];

明尼苏达州：= I;

结束;

标志[明尼苏达州]：= TRUE;

J： 1到n做

（J 明尼苏达州）和（A [1，明尼苏达州] + A [明尼苏达州，J]，A [1，J）和（标志[J] = FALSE），那么 BR / A [1，J] = [1，明尼苏达州] + A [明尼苏达州，J];

结束;

我：= 1到n做

写（ [1]）;

年底。

最短路径的Dijkstra算法

Dijkstra算法（迪杰斯特拉）是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。可以用堆优化。

Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。

Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式，Drew为了和下面要介绍的 A* 算法和 D* 算法表述一致，这里均采用OPEN,CLOSE表的方式。

其采用的是贪心法的算法策略

大概过程：

创建两个表，OPEN, CLOSE。

OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。

1． 访问路网中距离起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。

2． 从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。

3． 遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到OPEN表中。

4． 重复第2和第3步,直到OPEN表为空，或找到目标点。 #includeiostream#includevectorusing namespace std;void dijkstra(const int beg,//出发点              const vectorvectorint  adjmap,//邻接矩阵，通过传引用避免拷贝              vectorint dist,//出发点到各点的最短路径长度              vectorint path)//路径上到达该点的前一个点//负边被认作不联通//福利：这个函数没有用任何全局量，可以直接复制！{    const int NODE=adjmap.size();//用邻接矩阵的大小传递顶点个数，减少参数传递    dist.assign(NODE,-1);//初始化距离为未知    path.assign(NODE,-1);//初始化路径为未知    vectorbool flag(NODE,0);//标志数组，判断是否处理过    dist[beg]=0;//出发点到自身路径长度为0    while(1)    {        int v=-1;//初始化为未知        for(int i=0; i!=NODE; ++i)            if(!flag[i]dist[i]=0)//寻找未被处理过且                if(v0||dist[i]dist[v])//距离最小的点                    v=i;        if(v0)return;//所有联通的点都被处理过        flag[v]=1;//标记        for(int i=0; i!=NODE; ++i)            if(adjmap[v][i]=0)//有联通路径且                if(dist[i]0||dist[v]+adjmap[v][i]dist[i])//不满足三角不等式                {                    dist[i]=dist[v]+adjmap[v][i];//更新                    path[i]=v;//记录路径                }    }}int main(){    int n_num,e_num,beg;//含义见下    cout输入点数、边数、出发点：;    cinn_nume_numbeg;    vectorvectorint  adjmap(n_num,vectorint(n_num,-1));//默认初始化邻接矩阵    for(int i=0,p,q; i!=e_num; ++i)    {        cout输入第i+1条边的起点、终点、长度（负值代表不联通）：;        cinpq;        cinadjmap[p][q];    }    vectorint dist,path;//用于接收最短路径长度及路径各点    dijkstra(beg,adjmap,dist,path);    for(int i=0; i!=n_num; ++i)    {        coutbeg到i的最短距离为dist[i]，反向打印路径：;        for(int w=i; path[w]=0; w=path[w])            coutw-;        coutbeg'\n';    }}

用dijkstra算法解决最短路径问题c语言代码实现时怎样将每一个路径的顶点次序依次输出出来？

void Dijkstra(int n,int v,int dist[],int prev[],int **cost)

{

  int i;

  int j;

    int maxint = 65535;//定义一个最大的数值，作为不相连的两个节点的代价权值

    int *s ;//定义具有最短路径的节点子集s

  s = (int *)malloc(sizeof(int) * n);

    //初始化最小路径代价和前一跳节点值

    for (i = 1; i = n; i++)

    {

        dist[i] = cost[v][i];

        s[i] = 0;

        if (dist[i] == maxint)

        {

            prev[i] = 0;

        }

        else

        {

            prev[i] = v;

        }

    }

    dist[v] = 0;

    s[v] = 1;//源节点作为最初的s子集

    for (i = 1; i  n; i++)

    {

        int temp = maxint;

        int u = v;

        //加入具有最小代价的邻居节点到s子集

        for (j = 1; j = n; j++)

        {

            if ((!s[j])  (dist[j]  temp))

            {

                u = j;

                temp = dist[j];

            }

        }

        s[u] = 1;

        //计算加入新的节点后，更新路径使得其产生代价最短

        for (j = 1; j = n; j++)

        {

            if ((!s[j])  (cost[u][j]  maxint))

            {

                int newdist = dist[u] + cost[u][j];

                if (newdist  dist[j])

                {

                    dist[j] = newdist;

                    prev[j] = u;

                }

            }

        }

    }

}

//展示最佳路径函数

void ShowPath(int n,int v,int u,int *dist,int *prev)

{

 int j = 0;

 int w = u;

 int count = 0;

 int *way ;

 way=(int *)malloc(sizeof(int)*(n+1));

 //回溯路径

 while (w != v)

 {

  count++;

  way[count] = prev[w];

  w = prev[w];

 }

 //输出路径

 printf("the best path is:\n");

 for (j = count; j = 1; j--)

 {

  printf("%d - ",way[j]);

 }

 printf("%d\n",u);

}

//主函数，主要做输入输出工作

void main()

{

 int i,j,t;

  int n,v,u;

 int **cost;//代价矩阵

 int *dist;//最短路径代价

 int *prev;//前一跳节点空间

 printf("please input the node number: ");

  scanf("%d",n);

  printf("please input the cost status:\n");

 cost=(int **)malloc(sizeof(int)*(n+1));

  for (i = 1; i = n; i++)

  {

      cost[i]=(int *)malloc(sizeof(int)*(n+1));

  }

  //输入代价矩阵

  for (j = 1; j = n; j++)

  {

      for (t = 1; t = n; t++)

      {

          scanf("%d",cost[j][t]);

      }

  }

  dist = (int *)malloc(sizeof(int)*n);

  prev = (int *)malloc(sizeof(int)*n);

  printf("please input the source node: ");

  scanf("%d",v);

  //调用dijkstra算法  

  Dijkstra(n, v, dist, prev, cost);

  printf("*****************************\n");

 printf("have confirm the best path\n");

 printf("*****************************\n");

 for(i = 1; i = n ; i++)

 {

  if(i!=v)

  {

   printf("the distance cost  from node %d to node %d is %d\n",v,i,dist[i]);

   printf("the pre-node of node %d is node %d \n",i,prev[i]);

   ShowPath(n,v,i, dist, prev);

  }

 }

}

用Dijkstra算法求最短路径的MATLAB程序

你对图论的知识有了解吧~W是关联矩阵，s和t分别是起始点和终止节点的序号。返回的d为最短的加权路径长度,p为最优路径节点的序号向量。注意，这里W矩阵为0的点权值已经自动设为无穷大了。请参考《高等应用数学问题的 MATLAB一书》。我吧程序赋给你。

你做一个M函数用吧。

function [d,path]=dijkstra(W,s,t)

[n,m]=size(W);ix=(W==0);W(ix)=inf;

if n~=m,error('Square W required');end

visited(1:n)=0; dist(1:n)=inf;parent(1:n)=0;dist(s)=0;d=inf;

for i=1:(n-1),%求出每个节点与起始点的关系

ix=(visited==0);vec(1:n)=inf;vec(ix)=dist(ix);

[a,u]=min(vec);visited(u)=1;

for v=1:n,if (W(u,v)+dist(u)dist(v)),

dist(v)=dist(u)+W(u,v);parent(v)=u;

end;end;end

if parent(t)~=0,path=t;d=dist(t);%回溯最短路径

while t~=s,p=parent(t);path=[p path];t=p;end;

end;

希望对你有用

是否可以解决您的问题？

关于最短路的Dijkstra算法的程序源代码!

function [l,z]=Dijkstra(W)

n = size (W,1);

for i = 1 :n

l(i)=W(1,i);

z(i)=1;

end

i=1;

while i=n

for j =1 :n

if l(i)l(j)+W(j,i)

l(i)=l(j)+W(j,i);

z(i)=j;

if ji

if j~=1

i=j-1;

else

i=1;

end

end

end

i=i+1;

end

% W =[ 0 2 1 8 Inf Inf Inf Inf

% 2 0 Inf 6 1 Inf Inf Inf

% 1 Inf 0 7 Inf Inf 9 Inf

% 8 6 7 0 5 1 2 Inf

% Inf 1 Inf 5 0 3 Inf 9

% Inf Inf Inf 1 3 0 4 6

% Inf Inf 9 2 Inf 4 0 3

% Inf Inf Inf Inf 9 6 3 0 ];

得到实验数据结果：

L： 0 2 1 7 3 6 9 12

Z： 1 1 1 6 2 5 4 5

其中L为从1出发的结点到其他各个结点的路径长度，Z为路径上的结点，具体路径可由如下方法获得：

如查看1号到4号结点的路径，要经过6号1——》6——》4，而1号到6号要经过5号，即1——》5——》6——》4，进一步1号到5号要经过2号，即1——》2——》5——》6——》4，最后，因为1号可以直接到2号，故最短路径确定为1——》2——》5——》6——》4。

这里面加入了if ji，因为在每次i循环时，i代表的是目的结点，j代表的是通过结点j到达目标结点i，就是说如果当i为5时表示到前几个目标结点的最短路径已经确定了，但是如果此时发现经过的结点j《i产生了新的最短路径，则需要重新确定结点j为目标时的最短路径。

另附一个对比算法：

用于求从起始点s到其它各点的最短路

%D为赋权邻接矩阵，d为s到其它各点最短路径的长度，DD记载了最短路径生成树

function [d,DD]=dijkstra_aiwa(D,s)

[m,n]=size(D);

d=inf.*ones(1,m);

d(1,s)=0;

dd=zeros(1,m);

dd(1,s)=1;

y=s;

DD=zeros(m,m);

DD(y,y)=1;

counter=1;

while length(find(dd==1))m

for i=1:m

if dd(i)==0

d(i)=min(d(i),d(y)+D(y,i));

end

end

ddd=inf;

for i=1:m

if dd(i)==0d(i)ddd

ddd=d(i);

end

end

yy=find(d==ddd);

counter=counter+1;

DD(y,yy(1,1))=counter;

DD(yy(1,1),y)=counter;

y=yy(1,1);

dd(1,y)=1;

end

dijkstra最短路径算法代码的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于dijkstra算法能得出最短路径的最优解、dijkstra最短路径算法代码的信息别忘了在本站进行查找喔。