最短路径dijkstra算法c

Ⅰ 用C或C++实现求最短路径的Dijkstra算法

/* 用邻接矩阵表示的图的Dijkstra算法的源程序*/

#include<stdio.h>
#define MAXVEX 100

typedef char VexType;

typedef float AdjType;

typedef struct

{ VexType vexs[MAXVEX]; /* 顶点信息 */

AdjType arcs[MAXVEX][MAXVEX]; /* 边信息 */

int n; /* 图的顶点个数 */

}GraphMatrix;

GraphMatrix graph;

typedef struct {

VexType vertex; /* 顶点信息 */

AdjType length; /* 最短路径长度 */

int prevex; /* 从v0到达vi(i=1,2,…n-1)的最短路径上vi的前趋顶点 */

}Path;

Path dist[6]; /* n为图中顶点个数*/

#define MAX 1e+8

void init(GraphMatrix* pgraph, Path dist[])

{
int i; dist[0].length=0; dist[0].prevex=0;
dist[0].vertex=pgraph->vexs[0];

pgraph->arcs[0][0]=1; /* 表示顶点v0在集合U中 */

for(i=1; i<pgraph->n; i++) /* 初始化集合V-U中顶点的距离值 */

{ dist[i].length=pgraph->arcs[0][i];

dist[i].vertex=pgraph->vexs[i];

if(dist[i].length!=MAX)

dist[i].prevex=0;

else dist[i].prevex= -1;

}

}

void dijkstra(GraphMatrix graph, Path dist[])
{ int i,j,minvex; AdjType min;
init(&graph,dist); /* 初始化，此时集合U中只有顶点v0*/
for(i=1; i<graph.n; i++)
{ min=MAX; minvex=0;
for(j=1; j<graph.n; j++)
if( (graph.arcs[j][j]==0) && (dist[j].length<min) ) /*在V-U中选出距离值最小顶点*/
{ min=dist[j].length; minvex=j; }
if(minvex==0) break; /* 从v0没有路径可以通往集合V-U中的顶点 */
graph.arcs[minvex][minvex]=1; /* 集合V-U中路径最小的顶点为minvex */
for(j=1; j<graph.n; j++) /* 调整集合V-U中的顶点的最短路径 */
{ if(graph.arcs[j][j]==1) continue;
if(dist[j].length>dist[minvex].length+graph.arcs[minvex][j])
{ dist[j].length=dist[minvex].length+graph.arcs[minvex][j];
dist[j].prevex=minvex;
}
}
}
}

void initgraph()
{
int i,j;
graph.n=6;
for(i=0;i<graph.n;i++)
for(j=0;j<graph.n;j++)
graph.arcs[i][j]=(i==j?0:MAX);
graph.arcs[0][1]=50;
graph.arcs[0][2]=10;
graph.arcs[1][2]=15;
graph.arcs[1][4]=5;
graph.arcs[2][0]=20;
graph.arcs[2][3]=15;
graph.arcs[3][1]=20;
graph.arcs[3][4]=35;
graph.arcs[4][3]=30;
graph.arcs[5][3]=3;
graph.arcs[0][4]=45;
}

int main()
{
int i;
initgraph();
dijkstra(graph,dist);
for(i=0;i<graph.n;i++)
printf("(%.0f %d)",dist[i].length,dist[i].prevex);
return 0;
}
}
}
}

void initgraph()
{
int i,j;
graph.n=6;
for(i=0;i<graph.n;i++)
for(j=0;j<graph.n;j++)
graph.arcs[i][j]=(i==j?0:MAX);
graph.arcs[0][1]=50;
graph.arcs[0][2]=10;
graph.arcs[1][2]=15;
graph.arcs[1][4]=5;
graph.arcs[2][0]=20;
graph.arcs[2][3]=15;
graph.arcs[3][1]=20;
graph.arcs[3][4]=35;
graph.arcs[4][3]=30;
graph.arcs[5][3]=3;
graph.arcs[0][4]=45;
}

int main()
{
int i;
initgraph();
dijkstra(graph,dist);
for(i=0;i<graph.n;i++)
printf("(%.0f %d)",dist[i].length,dist[i].prevex);
return 0;
}
这个稍作改动就可以了。

Ⅱ 最短路径 - Dijkstra算法

算法每次都查找距离起始点最近的点，那么剩下的点距离起始点的距离一定比当前点大。

1.选定A节点并初始化，如上述步骤3所示

2.执行上述 4、5两步骤，找出U集合中路径最短的节点D 加入S集合，并根据条件 if ( 'D 到 B,C,E 的距离' + 'AD 距离' < 'A 到 B,C,E 的距离' ) 来更新U集合

3.这时候 A->B, A->C 都为3，没关系。其实这时候他俩都是最短距离，如果从算法逻辑来讲的话，会先取到B点。而这个时候 if 条件变成了 if ( 'B 到 C,E 的距离' + 'AB 距离' < 'A 到 C,E 的距离' ) ，如图所示这时候A->B距离 其实为 A->D->B

思路就是这样，往后就是大同小异了
算法结束

（图片来源于网络）

Dijkstra算法保证能找到一条从初始点到目标点的最短路径，只要所有的边都有一个非负的代价值。在上图中，粉红色的结点是初始结点，蓝色的是目标点，而类菱形的有色区域则是Dijkstra算法扫描过的区域。颜色最淡的区域是那些离初始点最远的，因而形成探测过程（exploration）的边境（frontier）。因而Dijkstra算法可以找到一条最短的路径，但是效率上并不高。

数据结构--Dijkstra算法最清楚的讲解

Ⅲ dijkstra算法是什么

dijkstra算法最短路径算法。

Dijkstra是典型最短路径算法，用于计算一个节点到其他节点的最短路径。该算法使用的是贪心策略：每次都找出剩余顶点中与源点距离最近的一个顶点。

给定一带权图，图中每条边的权值是非负的，代表着两顶点之间的距离。指定图中的一顶点为源点，找出源点到其它顶点的最短路径和其长度的问题，即是单源最短路径问题。

Dijkstra的原理

（1）初始化时，S只含有源节点。

（2）从U中选取一个距离v最小的顶点k加入S中（该选定的距离就是v到k的最短路径长度）。

（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源节点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值是顶点k的距离加上k到u的距离。

Ⅳ dijkstra算法是什么

Dijkstra算法是由荷兰计算机科学家狄克斯特拉（Dijkstra）于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。

其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。

不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。

举例来说，如果图中的顶点表示城市，而边上的权重表示着城市间开车行经的距离。Dijkstra算法可以用来找到两个城市之间的最短路径。

Dijkstra算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。我们以V表示G中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。（u,v)表示从顶点u到v有路径相连。我们以E所有边的集合，而边的权重则由权重函数w: E→[0,∞］定义。

因此，w(u,v)就是从顶点u到顶点v的非负花费值（cost)。边的花费可以想象成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。

已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径（i.e.最短路径）。这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。

Ⅳ 用C++求dijkstra算法求最短路径

/**************************************************************
* 给定一个带权有向图G = (V，E)，其中每条边的权是一个非负整数。*
* 另外还给定V中的一个顶点，称为源。现在我们要计算从源到所有其 *
* 他各顶点的最短路长度。这里路径长度是路上各边权之和。这个问 *
* 题通常称为单源最短路径问题。 *
***************************************************************/
#include<iostream.h>

#define INFINITE 100

void main()
{
int j,i,n,k,t,**w,*s,*p,*d;

cout<<"input the value of n:";
cin>>n;
cout<<endl;

d = new int[n];
s = new int[n];
p = new int[n];
w = new int*[n];

for(i = 0; i < n; i++)
{
w[i] = new int[n];
}

for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
cin>>w[i][j];

for(s[0] = 1,i = 1; i < n; i++)
{
s[i] = 0;
d[i] = w[0][i];
if(d[i] < INFINITE)
p[i]=0;
else
p[i]=-1;
}

for(i = 1; i < n; i++)
{
t = INFINITE;
k = 1;
for(j = 1; j < n; j++)
if((!s[j]) && (d[j] < t))
{
t = d[j];
k = j;
}
s[k]=1;//point k join the S
for (j = 1; j < n; j++)
if((!s[j]) && (d[j] > d[k] + w[k][j]))
{
d[j] = d[k] + w[k][j];
p[j] = k;
}

}
cout<<"从源点到其它顶点的最短距离依次如下：";
for(i=1;i<n;i++) cout<<d[i]<<" ";
cout<<endl;

}
/*********
顶点个数用n表示，这里给出的例子n=6
100 1 12 100 100 100
100 100 9 3 100 100
100 100 100 100 5 100
100 100 4 100 13 15
100 100 100 100 100 4
100 100 100 100 100 100
具体例子见 电子工业出版社 《算法设计技巧与分析》148页
************/

Ⅵ 数学建模第四章 图论 part4.2最短路径问题-Dijkstra算法

1.Dijkstra算法介绍

算法特点：

迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

算法的思路

Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。 

然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点， 

然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。 

然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。

2、Dijkstra算法示例演示

我求下图，从顶点v1到其他各个顶点的最短路径.

首先第一步，我们先声明一个dis数组，该数组初始化的值为：

我们的顶点集T的初始化为：T={v1}

既然是求 v1顶点到其余各个顶点的最短路程，那就先找一个离 1 号顶点最近的顶点。通过数组 dis 可知当前离v1顶点最近是 v3顶点。当选择了 2 号顶点后，dis[2]（下标从0开始）的值就已经从“估计值”变为了“确定值”，即 v1顶点到 v3顶点的最短路程就是当前 dis[2]值。将V3加入到T中。 

为什么呢？因为目前离 v1顶点最近的是 v3顶点，并且这个图所有的边都是正数，那么肯定不可能通过第三个顶点中转，使得 v1顶点到 v3顶点的路程进一步缩短了。因为 v1顶点到其它顶点的路程肯定没有 v1到 v3顶点短.

OK，既然确定了一个顶点的最短路径，下面我们就要根据这个新入的顶点V3会有出度，发现以v3 为弧尾的有： < v3,v4 >,那么我们看看路径：v1–v3–v4的长度是否比v1–v4短，其实这个已经是很明显的了，因为dis[3]代表的就是v1–v4的长度为无穷大，而v1–v3–v4的长度为：10+50=60，所以更新dis[3]的值,得到如下结果： 

因此 dis[3]要更新为 60。这个过程有个专业术语叫做“松弛”。即 v1顶点到 v4顶点的路程即 dis[3]，通过 < v3,v4> 这条边松弛成功。这便是 Dijkstra 算法的主要思想：通过“边”来松弛v1顶点到其余各个顶点的路程。

然后，我们又从除dis[2]和dis[0]外的其他值中寻找最小值，发现dis[4]的值最小，通过之前是解释的原理，可以知道v1到v5的最短距离就是dis[4]的值，然后，我们把v5加入到集合T中，然后，考虑v5的出度是否会影响我们的数组dis的值，v5有两条出度：< v5,v4>和 < v5,v6>,然后我们发现：v1–v5–v4的长度为：50，而dis[3]的值为60，所以我们要更新dis[3]的值.另外，v1-v5-v6的长度为：90，而dis[5]为100，所以我们需要更新dis[5]的值。更新后的dis数组如下图： 

然后，我们使用同样原理，分别确定了v6和v2的最短路径，最后dis的数组的值如下： 

因此，从图中，我们可以发现v1-v2的值为：∞，代表没有路径从v1到达v2。所以我们得到的最后的结果为：

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

voidDijkstra(intn,intv,intdist[],intprev[],int**cost)
{
inti;
intj;
intmaxint=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++)
{
inttemp=maxint;
intu=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))
{
intnewdist=dist[u]+cost[u][j];
if(newdist<dist[j])
{
dist[j]=newdist;
prev[j]=u;
}
}
}
}
}
//展示最佳路径函数
voidShowPath(intn,intv,intu,int*dist,int*prev)
{
intj=0;
intw=u;
intcount=0;
int*way;
way=(int*)malloc(sizeof(int)*(n+1));
//回溯路径
while(w!=v)
{
count++;
way[count]=prev[w];
w=prev[w];
}
//输出路径
printf("thebestpathis:
");
for(j=count;j>=1;j--)
{
printf("%d->",way[j]);
}
printf("%d
",u);
}
//主函数，主要做输入输出工作
voidmain()
{
inti,j,t;
intn,v,u;

int**cost;//代价矩阵
int*dist;//最短路径代价
int*prev;//前一跳节点空间
printf("pleaseinputthenodenumber:");
scanf("%d",&n);
printf("pleaseinputthecoststatus:
");

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("pleaseinputthesourcenode:");
scanf("%d",&v);
//调用dijkstra算法
Dijkstra(n,v,dist,prev,cost);
printf("*****************************
");
printf("haveconfirmthebestpath
");
printf("*****************************
");
for(i=1;i<=n;i++)
{
if(i!=v)
{
printf("thedistancecostfromnode%dtonode%dis%d
",v,i,dist[i]);
printf("thepre-nodeofnode%disnode%d
",i,prev[i]);
ShowPath(n,v,i,dist,prev);
}
}
}