dijkstra算法的实现
❶ C语言实现Dijkstra算法
#include<stdlib.h> #define INFINITY 1000000000 //最大距离
#define MAX_NODES 1024 //最大节点数
int n,dist[MAX_NODES][MAX_NODES]; //dist[i][j]表示从 i 到 j 的距离 void shortest_path(int s, int t, int path[])
{
struct state
{
int predecessor; //前驱节点
int length; //到起始点的距离
enum {permanent, tentative} label;
}state[MAX_NODES];
int i,k,min;
struct state * p;
for(p=&state[0]; p<&state[n]; p++)
{
p->predecessor = -1;
p->length = INFINITY;
p->label = tentative;
}
state[t].length = 0;
state[t].label = permanent;
k = t; //k 是当前工作节点
do
{
for(i=0; i<n; i++)
{
if(dist[k][i]!=0 && state[i].label==tentative)
{
if(state[k].length+dist[k][i]<state[i].length)
{
state[i].length = state[k].length+dist[k][i];
state[i].predecessor = k;
}
}
}
k=0;
min=INFINITY;
for(i=0; i<n; i++)
{
if(state[i].label==tentative && state[i].length<min)
{
k=i;
min=state[i].length;
}
}
state[k].label = permanent;
}while(k!=s);
i=0;
k=s;
do
{
path[i++] = k;
k = state[k].predecessor;
}while(k>=0);
}
❷ Dijkstra算法的原理和C的编程实现
.Dijkstra算法求单源最短路径
语法：result=Dijkstra(Graph G,int n,int s,int t, int path[]);
参数：
G：
图，用邻接矩阵表示
n：
图的顶点个数
s：
开始节点
t：
目标节点
path[]：
用于返回由开始节点到目标节点的路径
返回值：
最短路径长度
注意：
输入的图的权必须非负
顶点标号从0开始
用如下方法打印路径：
i=t;
while (i!=s)
{
printf("%d<--",i+1);
i=path[i];
}
printf("%d\n",s+1);
源程序：
int Dijkstra(Graph G,int n,int s,int t, int path[])
{
int i,j,w,minc,d[max_vertexes],mark[max_vertexes];
for (i=0;i<n;i++) mark[i]=0;
for (i=0;i<n;i++)
{ d[i]=G[s][i];
path[i]=s; }
mark[s]=1;path[s]=0;d[s]=0;
for (i=1;i<n;i++)
{
minc=infinity;
w=0;
for (j=0;j<n;j++)
if ((mark[j]==0)&&(minc>=d[j])) {minc=d[j];w=j;}
mark[w]=1;
for (j=0;j<n;j++)
if ((mark[j]==0)&&(G[w][j]!=infinity)&&(d[j]>d[w]+G[w][j]))
{ d[j]=d[w]+G[w][j];
path[j]=w; }
}
return d[t];
}
原理：（1）初始时，S只包含源点，即S=，v的距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或 ∞(若u不是v的出边邻接点）。 （2）从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。 （3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值为顶点k的距离加上边上的权。 （4）重复步骤（2）和（3）直到所有顶点都包含在S中。
❸ 希望熟悉c++中Dijkstra算法实现的编程高手们解答！！
if(dist[i] == maxint)
prev[i] = 0;
else
prev[i] = v;
这个表示的是取到当前最短路是经过哪个点过来的。记录路径，如果要输出路径的话就一直接prev就可以了。
❹ Dijkstra算法的C语言实现：文件读取、图的存储、算法实现、路径输出
要现写，你的分太少了，至少也200分吧，我给你个模板，时间复杂度为nLOG2(n)：
dij邻接阵
#include <algorithm>
#include <deque>
#include <queue>
#include <iostream>
using namespace std;
#define MN 1001
#define INF (1<<29)
int graf[MN][MN];
struct node
{
int v;
int dis;
node(int vv,int dd){v=vv;dis=dd;}
node(){}
};
bool operator < (const node aa,const node bb)
{
return aa.dis>bb.dis;//最小堆
}
int dis[MN];
void dijkstra(int s,int n)//s是源点,[1..n]
{
node tmp;
int i,w;
for(i=1;i<=n;++i){dis[i]=INF;}
priority_queue < node,deque<node> > Q;
Q.push(node(s,0));
for(dis[s]=0;!Q.empty();)
{
tmp=Q.top();Q.pop();
if(tmp.dis!=dis[tmp.v])continue;
for(i=1;i<=n;++i)
{
w=graf[tmp.v][i];
if(w!=INF&&dis[tmp.v]+w<dis[i])
{
//必要时可保存路径pre[i]=tmp.v
dis[i]=dis[tmp.v]+w;
Q.push(node(i,dis[i]));
}
}
}
}
❺ Dijkstra算法的Pascal实现
dijkstra算法的Pascal实现：
program dijkstra;
var
a:array[1..100,1..100]of integer;
flag:array[1..100]of boolean;
w,x,n,i,j,min,minn:integer;
begin
readln(n);
for i:=1 to n do
begin
for j:=1 to n do read(a[i,j]);
readln;
end;
fillchar(flag,sizeof(flag),false);
flag[1]:=true;
minn:=1;
for x:=2 to n do
begin
min:=32767;
for i:=2 to n do
if (a[1,i]<min)and(flag=false) then
begin
min:=a[1,i];
minn:=i;
end;
flag[minn]:=true;
for j:=1 to n do
if (j<>minn) and (a[1,minn]+a[minn,j]<a[1,j]) and(flag[j]=false) then
a[1,j]:=a[1,minn]+a[minn,j];
end;
for i:=1 to n do
write(a[1,i],' ');
end.
4
0 100 30 999
100 0 99 10
30 99 0 99
999 10 99 0
程序输出：0 100 30 110
❻ 用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;
}
这个稍作改动就可以了。
❼ 迪杰斯特拉算法的算法实现
· 算法思想
设给定源点为Vs，S为已求得最短路径的终点集，开始时令S={Vs} 。当求得第一条最短路径(Vs ，Vi)后，S为{Vs，Vi} 。根据以下结论可求下一条最短路径。
设下一条最短路径终点为Vj ，则Vj只有：
◆ 源点到终点有直接的弧<Vs，Vj>；
◆ 从Vs 出发到Vj 的这条最短路径所经过的所有中间顶点必定在S中。即只有这条最短路径的最后一条弧才是从S内某个顶点连接到S外的顶点Vj 。
若定义一个数组dist[n]，其每个dist[i]分量保存从Vs 出发中间只经过集合S中的顶点而到达Vi的所有路径中长度最小的路径长度值，则下一条最短路径的终点Vj必定是不在S中且值最小的顶点，即：
dist[i]=Min{ dist[k]| Vk∈V-S }
利用上述公式就可以依次找出下一条最短路径。
· 示例程序
· 算法思想
var a:array[1..100,1..100]of integer;//邻接矩阵
flag:array[1..100] of boolean;//已经找到最短路径的节点标志
path:array[1..100]of integer;
w,x,n,i,j,min,minn,k:integer;
begin
readln(n,k);for i:=1 to n do//读取邻接矩阵,无路径写-1
begin
for j:=1 to n do
begin
read(a[i,j]);
If a[i,j]=-1 then a[I,j]:=maxint;
end;
readln;
end;
fillchar(flag,sizeof(flag),false);//标明所有节点都未找到最短路径
flag[k]:=true; //源节点除外
fillword(path,sizeof(path) div 2,k);
path[k]:=0;
minn:=k;//标记最小的点for x:=2 to n do
begin
min:=32767;//标记要找下一个最短路径点的距离
for i:=1 to n do//找下一点点
if (a[k,i]<min) and (flag[i]=false) then
begin
min:=a[k,i];
minn:=i;
end;
flag[minn]:=true;//标记下一个点的找到
for j:=1 to n do //更新最短路径
if (j<>minn) and (a[k,minn]+a[minn,j]<a[k,j]) and (flag[j]=false) then
begin
a[k,j]:=a[k,minn]+a[minn,j];
path[j]:=minn;
end;
end;
for i:=1 to n do write(a[k,i],' ');//输出源点到各个点的距离
writeln;
for i:=1 to n do write(path[i],' ');//输出源点到各个点的距离
end.
求采纳（空格被网络吃了……）
❽ 以邻接表作存储结构实现求源点到其余各顶点的最短路径的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("创建失败 ");
}
}
(8)dijkstra算法的实现扩展阅读：
要求带权有向图中某一顶点到其他各顶点的最短路径，常用Dijkstra算法，该算法基本思想是，先将图的顶点分为两个集合，一个为已求出最短路径的终点集合（开始为原点v1），另一个为还未求出最短路径的顶点集合（开始为除v1外的全部结点），然后按最短路径长度的递增顺序逐个将第二个集合的顶点加到第一组中。
算法中使用dist数组，dist[i]表示目前已经找到、v1到vi的当前最短路径，否则为MAX；path数组，作为是否找到该点最短路径的标志，path[i]==MIN表示为未找到，否则为最短路径值。
❾ dijkstra算法的c实现
#include <stdlib.h>
#define INF 1000000000
#define MAXV 200
typedef struct Graph{
int n;
int w[MAXV][MAXV];
};
int d[MAXV];
int pre[MAXV];
void init_single_source(Graph *G,int s) {
for (int i=0;i<G->n;i++) {
d[i]=INF;
pre[i]=-1;
}
d[s]=0;
}
void relax(int u,int v,Graph *G) {
if (d[v]>d[u]+G->w[u][v]) {
d[v]=d[u]+G->w[u][v];
pre[v]=u;
}
}
int dijkstra(Graph *G,int s) {
init_single_source(G,s);
int S[MAXV],i,j,u,min;
for (i=0;i<G->n;i++) S[i]=0;
for (i=0;i<G->n;i++) {
min=INF;
u=-1;
for (j=0;j<G->n;j++) if (S[j]==0 && d[j]<min) {
u=j;
min=d[j];
}
S[u]=-1;
for (j=0;j<G->n;j++) if (S[j]==0) relax(u,j,G);
}
}
❿ 求Dijkstra算法的C语言实现
//Dijkstra算法 C语言实现 2008-08-26 12:07 #include<stdio.h>
#include<stdlib.h> #define INFINITY 1000000000 //最大距离
#define MAX_NODES 1024 //最大节点数
int n,dist[MAX_NODES][MAX_NODES]; //dist[i][j]表示从 i 到 j 的距离 void shortest_path(int s, int t, int path[])
{
struct state
{
int predecessor; //前驱节点
int length; //到起始点的距离
enum {permanent, tentative} label;
}state[MAX_NODES];
int i,k,min;
struct state * p;
for(p=&state[0]; p<&state[n]; p++)
{
p->predecessor = -1;
p->length = INFINITY;
p->label = tentative;
}
state[t].length = 0;
state[t].label = permanent;
k = t; //k 是当前工作节点
do
{
for(i=0; i<n; i++)
{
if(dist[k][i]!=0 && state[i].label==tentative)
{
if(state[k].length+dist[k][i]<state[i].length)
{
state[i].length = state[k].length+dist[k][i];
state[i].predecessor = k;
}
}
}
k=0;
min=INFINITY;
for(i=0; i<n; i++)
{
if(state[i].label==tentative && state[i].length<min)
{
k=i;
min=state[i].length;
}
}
state[k].label = permanent;
}while(k!=s);
i=0;
k=s;
do
{
path[i++] = k;
k = state[k].predecessor;
}while(k>=0);
}