dijkstra算法求最短路径

❶ 数据结构中迪杰斯特拉算法求最短路径

dijkstra算法本身求的是一点到其他所有点的最短距离，而不是具体的路径，因此还需要一个额外的数组来记录推导最短距离的过程中经过的每一个结点，这样才能求出这个最短距离的具体路径。

❷ 用dijkstra算法求a到f的最短路径

#include<stdio.h>
inta[205][205];//记录邻接矩阵
intdist[205];//到每个点的最短路
intm,n;//m条路，n个点
constintINF=0xfffffff;
voidinit()//初始化数据
{
for(inti=0;i<n;i++)
for(intj=0;j<n;j++)
a[i][j]=(i==j?0:INF);
}

voiddijkstra(intu)//从第u个点开始走
{
intsign[205]={0};//标记走过否
intx=u;
inti,j;
for(i=0;i<n;i++)//初始化到各点距离
dist[i]=a[x][i];
dist[x]=0;//到本身距离为0
sign[x]=1;//改点以走过
for(i=1;i<=n-2;i++)
{
intmin=INF;
for(j=0;j<n;j++)//在为走过的点中取距离x最短的点
{
if(!sign[j]&&min>dist[j])
{
min=dist[j];
x=j;
}
}
sign[x]=1;//标记，已走过

for(j=0;j<n;j++)//x以改变，更新dist[]值
{
if(!sign[j]&&dist[x]+a[x][j]<dist[j]&&a[x][j]<INF)
dist[j]=a[x][j]+dist[x];
}
}
}
intmain()
{
inti;
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
for(i=0;i<m;i++)
{
intx,y,z;
scanf("%d%d%d",&x,&y,&z);
if(z<a[x][y])//取两点多条路最小路
a[x][y]=z;
if(z<a[y][x])
a[y][x]=z;
}
ints,t;
scanf("%d%d",&s,&t);
dijkstra(s);

if(dist[t]<2000000)
printf("%d
",dist[t]);
else
printf("-1
");
}
return0;
}

参考链接 ：http://blog.csdn.net/ouyangying123/article/details/38706957

❸ 求出最短路径，要过程，用Dijkstra算法。。。

从v1开始遍历
v2 = 2;
v3 = 5;
v2较小所以跳到v2
v3 = 4;

v4 = 6;
v5 = 8;
v3较小所以跳到v3
v4 = 5;
v6 = 7;
v4较小所以跳到v4
v6 = 6;
v7 = 9;
v6较小所以跳到v6
v7 = 8;

所以最后结果v1 -> v7最短路径为v1->v2->v3->v4->v6->v7,最短路径长度为8

❹ 利用Dijkstra算法求下图中从顶点1到其它各顶点间的最短路径，按下面表格形式

v1到v2：10为最短路径；

v1到v3：7为最短路径；

v1到v4：8为最短路径；

v1到v5：v1-> v2 -> v5 =10+6= 16；v1v3v5=7+9=16;v1v4v6v5=8+5+2=15; 15为最短路径；

v1到v6：v1v2v3v6=10+2+9=21；v1v3v6=7+9=16；v1v4v6=8+5=13；13为最短路径；

v1到v7：v1v2v5v7=10+6+20=36；v1v3v5v7=7+9+20=36；v1v3v6v7=7+9+30=46；

v1v4v6v7=8+5+30=42；v1v4v6v5v7=35；35为最短路径

Dijkstra：

求单源、无负权的最短路。时效性较好，时间复杂度为O（V*V+E）。源点可达的话，O（V*lgV+E*lgV）=>O（E*lgV）。当是稀疏图的情况时，此时E=V*V/lgV，所以算法的时间复杂度可为O（V^2）。若是斐波那契堆作优先队列的话，算法时间复杂度，则为O（V*lgV + E）。

以上内容参考：网络-最短路径算法

❺ 数据结构 dijkstra算法 最短路径

你这个算法到这步，还没结束。
因为S=【1,2,4】，U=【3】。下面应该把【3】，加入到S中。进行路径的判断。
3加入进来，发现1-》2-》4大于1-》3-》4。所以1-》4的距离会重新算。

❻ 以邻接表作存储结构实现求源点到其余各顶点的最短路径的Dijkstra算法

具体算法为：

//Dijkstra求单源最短路径

#include<stdio.h>

#define N 20 //图的顶点最多数

#define MAX 1000

#define MIN -1

typedef int ElemType;//图的顶点标识，这里为自然数

//图的结点结构

typedef struct ArcNode{

ElemType adjvex;//图的顶点 （该弧指向顶点的位置）

struct ArcNode *nextarc;//指向下一条弧的指针

int info//该弧权值

}ArcNode;

//表头结点表

typedef struct VertexNode{

ElemType data;

ArcNode *firstarc;

}VertexNode;

//图

typedef struct AdjList{

VertexNode vertex[N];

int vexnum;//图的顶点数

int arcnum;//弧数;

int kind;//图的种类（kind=1为有向图）

int dist[N];//图的路径长度

int path[N];//辅助数组

}AdjList;

//边

typedef struct{

int i;

int j;

int f;

}Side;

//邻接表法创建图

int CreateDAG(AdjList *L){

int i,j;

ArcNode *p=NULL;

//测试用例

Side S[N];

S[0].i=1;S[0].j=3;S[0].f=10;

S[1].i=1;S[1].j=5;S[1].f=30;

S[2].i=1;S[2].j=6;S[2].f=100;

S[3].i=2;S[3].j=3;S[3].f=5;

S[4].i=3;S[4].j=4;S[4].f=50;

S[5].i=4;S[5].j=6;S[5].f=10;

S[6].i=5;S[6].j=6;S[6].f=60;

S[7].i=5;S[7].j=4;S[7].f=20;

for(i=1;i<7;i++){

L->vertex[i].data=i;

L->dist[i]=MAX;//设为最大值，表示不可达

L->path[i]=MIN;//设为最小值，表示尚未初始化

//L->vertex[i].indegree=0;

L->vertex[i].firstarc=NULL;

}

L->kind=1;

L->vexnum=6;

L->arcnum=8;

for(i=0;i<8;i++){

p=(ArcNode *)malloc(sizeof(ArcNode));

p->adjvex=S[i].j;

p->info=S[i].f;

p->nextarc=L->vertex[(S[i].i)].firstarc;

L->vertex[(S[i].i)].firstarc=p;

if(S[i].i==1){//初始顶点为1

L->dist[(S[i].j)]=S[i].f;

//L->path[(S[i].j)]=S[i].f;

}

// L->vertex[(S[i].j)].indegree++;

}

return 1;

}

//输出邻接表存储

void PrintALGraph(AdjList *L){

ArcNode *p=NULL;

int i,k=0;

for(i=1;i<=L->vexnum;i++){

k=L->vertex[i].data;

printf("V%d",k);

// printf(" 入度为%d 邻接点有 ",(L->vertex[i].indegree));

p=L->vertex[k].firstarc;

while(p!=NULL){

printf(" ->%d",p->adjvex);

p=p->nextarc;

}

printf(" ");

}

}

//Dijkstra求单源最短路径

void Dijkstra(AdjList *L){

int i=1,j,k=0;

Side s;

L->path[1]=0;

ArcNode *p=NULL;

while(k<10){

s.f=MAX;

for(i=1;i<=L->vexnum;i++){

if(L->path[i]!=MIN){

p=L->vertex[i].firstarc;

if(p!=NULL){

while(p!=NULL){

if(s.f>p->info&&L->path[(p->adjvex)]==MIN){

s.f=p->info;

s.i=i;

s.j=p->adjvex;

}

p=p->nextarc;

}

}

}

}

if(s.f==MAX){

}else if(L->dist[(s.j)]>L->dist[(s.i)]+s.f){

L->dist[(s.j)]=L->dist[(s.i)]+s.f;

L->path[(s.j)]=L->dist[(s.j)];

}else{

L->path[(s.j)]=L->dist[(s.j)];

}

k++;

}

//输出

printf("输出最短路径: ");

for(i=1;i<=L->vexnum;i++){

if(L->dist[i]==1000||i==1){

printf("v1到v%d不存在最短路径 ",i);

}else{

printf("v1到v%d的最短路径是%d ",i,L->dist[i]);

}

printf("path is %d ",L->path[i]);

}

}

int main(){

AdjList *L=(AdjList *)malloc(sizeof(AdjList));

if(CreateDAG(L)==1){

PrintALGraph(L);

Dijkstra(L);

}else{

printf("创建失败 ");

}

}

(6)dijkstra算法求最短路径扩展阅读：

要求带权有向图中某一顶点到其他各顶点的最短路径，常用Dijkstra算法，该算法基本思想是，先将图的顶点分为两个集合，一个为已求出最短路径的终点集合（开始为原点v1），另一个为还未求出最短路径的顶点集合（开始为除v1外的全部结点），然后按最短路径长度的递增顺序逐个将第二个集合的顶点加到第一组中。

算法中使用dist数组，dist[i]表示目前已经找到、v1到vi的当前最短路径，否则为MAX；path数组，作为是否找到该点最短路径的标志，path[i]==MIN表示为未找到，否则为最短路径值。

❼ 用dijkstra算法计算源点到个结点的最短路径....谢谢亲爱的朋友~ 详细答案

(这里描述的是从节点1开始到各点的dijkstra算法，其中Wa->b表示a->b的边的权值，d(i)即为最短路径值)
1． 置集合S={2,3,...n}, 数组d(1)=0, d(i)=W1->i(1,i之间存在边) or +无穷大(1.i之间不存在边) 2． 在S中，令d(j)=min{d(i),i属于S}，令S=S-{j}，若S为空集则算法结束，否则转3
3． 对全部i属于S,如果存在边j->i，那么置d(i)=min{d(i), d(j)+Wj->i}，转2

❽ 单源最短路径的Dijkstra算法

将图G中所有的顶点V分成两个顶点集合S和T。以v为源点已经确定了最短路径的终点并入S集合中，S初始时只含顶点v,T则是尚未确定到源点v最短路径的顶点集合。然后每次从T集合中选择S集合点中到T路径最短的那个点，并加入到集合S中，并把这个点从集合T删除。直到T集合为空为止。
具体步骤
1、选一顶点v为源点，并视从源点v出发的所有边为到各顶点的最短路径（确定数据结构：因为求的是最短路径，所以①就要用一个记录从源点v到其它各顶点的路径长度数组dist[],开始时，dist是源点v到顶点i的直接边长度，即dist中记录的是邻接阵的第v行。②设一个用来记录从源点到其它顶点的路径数组path[],path中存放路径上第i个顶点的前驱顶点）。
2、在上述的最短路径dist[]中选一条最短的，并将其终点（即<v,k>）k加入到集合s中。
3、调整T中各顶点到源点v的最短路径。 因为当顶点k加入到集合s中后，源点v到T中剩余的其它顶点j就又增加了经过顶点k到达j的路径,这条路径可能要比源点v到j原来的最短的还要短。调整方法是比较dist[k]+g[k,j]与dist[j]，取其中的较小者。
4、再选出一个到源点v路径长度最小的顶点k,从T中删去后加入S中，再回去到第三步，如此重复，直到集合S中的包含图G的所有顶点。 SPFA实际上是Bellman-Ford基础上的队列优化
SPFA(G,w,s)
1. INITIALIZE-SINGLE-SOURCE(G,s)
2. INITIALIZE-QUEUE(Q)
3. ENQUEUE(Q,s)
4. While Not EMPTY(Q)
5. Do u<-DLQUEUE(Q)
6. For 每条边(u,v) in E[G]
7. Do tmp<-d[v]
8. Relax(u,v,w)
9. If (d[v] < tmp) and (v不在Q中)
10. ENQUEUE(Q,v)
c++：
boolSPFA(intsource)
{
deque<int>dq;
inti,j,x,to;
for(i=1;i<=nodesum;i++)
{
in_sum[i]=0;
in_queue[i]=false;
dist[i]=INF;
path[i]=-1;
}
dq.push_back(source);
in_sum[source]++;
dist[source]=0;
in_queue[source]=true;
//初始化完成
while(!dq.empty())
{
x=dq.front();
dq.pop_front();
in_queue[x]=false;
for(i=0;i<adjmap[x].size();i++)
{
to=adjmap[x][i].to;
if((dist[x]<INF)&&(dist[to]>dist[x]+adjmap[x][i].weight))
{
dist[to]=dist[x]+adjmap[x][i].weight;
path[to]=x;
if(!in_queue[to])
{
in_queue[to]=true;
in_sum[to]++;
if(in_sum[to]==nodesum)
return false;
if(!dq.empty())
{
if(dist[to]>dist[dq.front()])
dq.push_back(to);
else
dq.push_front(to);
}
else
dq.push_back(to);
}
}
}
}
returntrue;
}

❾ 利用Dijkstra算法求有向网图的最短路径

v1到v2：10为最短路径；
v1到v3：7为最短路径；
v1到v4:8为最短路径；
v1到v5：v1->
v2
->
v5
=10+6=
16；v1v3v5=7+9=16;v1v4v6v5=8+5+2=15;
15为最短路径；
v1到v6：v1v2v3v6=10+2+9=21；v1v3v6=7+9=16；v1v4v6=8+5=13；13为最短路径；
v1到v7：v1v2v5v7=10+6+20=36；v1v3v5v7=7+9+20=36；v1v3v6v7=7+9+30=46；
v1v4v6v7=8+5+30=42；v1v4v6v5v7=35；35为最短路径