迪杰斯特拉c语言

1. 解释一下dijkstra算法这个计算过程的意思 怎么算的

最近也看到这个算法，不过主要是通过c语言介绍的，不太一样，但基本思想差不多。下面只是我个人的看法不一定准确。
Dijkstra算法主要解决指定某点(源点)到其他顶点的最短路径问题。
基本思想：每次找到离源点最近的顶点，然后以该顶点为中心(过渡顶点)，最终找到源点到其余顶点的最短路。

t=1：令源点(v_0)的标号为永久标号(0,λ)(右上角加点), 其他为临时(+无穷,λ). 就是说v_0到v_0的距离是0，其他顶点到v_0的距离为+无穷。t=1时，例5.3上面的步骤(2)(3)并不能体现

t=2：第1步v_0(k=0)获得永久标号，记L_j为顶点标号当前的最短距离(比如v_0标号(0,λ)中L_0=0), 边(v_k,v_j)的权w_kj. 步骤(2)最关键，若v_0与v_j之间存在边，则比较L_k+w_kj与L_j, 而L_k+w_kj=L_0+w_0j<L_j=+无穷。
这里只有v_1,v_2与v_0存在边，所以当j=1,2时修改标号, 标号分别为(L_1, v_0)=(1, v_0), (L_2, v_0)=(4, v_0), 其他不变。步骤(3)比较所有临时标号中L_j最小的顶点, 这里L_1=1最小，v_1获得永久标号(右上角加点)。

t=3: 第2步中v_1获得永久标号(k=1), 同第2步一样，通过例5.3上面的步骤(2)(3)，得到永久标号。 步骤(2),若v_1与v_j(j=2,3,4,5(除去获得永久标号的顶点))之间存在边，则比较L_1+w_1j与L_j。这里v_1与v_2，v_3，v_,4存在边，
对于v_2, L_1+w_12=1+2=3<L_2=4, 把v_2标号修改为(L_1+w_12, v_1)=(3, v_1);
对于v_3, L_1+w_13=1+7=8<L_3=+无穷, 把v_3标号修改为(L_1+w_13, v_1)=(8, v_1);
对于v_4, L_1+w_14=1+5=6<L_4=+无穷, 把v_4标号修改为(L_1+w_14, v_1)=(6, v_1);
v_5与v_1不存在边，标号不变。步骤(3), 找这些标号L_j最小的顶点，这里v_2标号最小

t=4: k=2, 与v_2存在边的未获得永久标号的顶点只有v_4, 比较L_2+w_24=3+1=4<L_4=6, 把v_4标号修改为(L_2+w_24, v_2)=(4, v_2); 其他不变。步骤(3), L_4=4最小。

t=5: k=4, 同理先找v_4邻接顶点，比较，修改标号，找L_j最小
t=6: 同理

啰嗦的这么多，其实步骤(2)是关键，就是通过比较更新最短路径，右上角标点的就是距离源点最近的顶点，之后每一步就添加一个新的”源点”，再找其他顶点与它的最短距离。

迪杰斯特拉算法(Dijkstra)(网络)：
http://ke..com/link?url=gc_mamV4z7tpxwqju6BoqxVOZ_josbPNcGKtLYJ5GJsJT6U28koc_#4
里面有个动图，更形象地说明了该算法的过程。(其中每次标注的一个红色顶点out就和你的这本书中获得永久标号是相似的)

2. 用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);
}
}
}

3. 求迪杰斯特拉算法c语言实现

*迪杰斯特拉算法算法步骤：
（1）初始时，S只包含源点。
（2）从U中选取一个距离v最小的顶点k加入S中（该选定的距离就是v到k的最短路径长度）。
（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
（4）重复步骤（2）和（3）直到所有顶点都包含在S中。
*/
#include<iostream.h>
#include<string.h>
#include<stdlib.h>
#define M 999
void main(){
int cost[6][6]={
{M,M,10,M,30,100},
{M,M,M, M, M,M },
{M,5,M, 50,M,M },
{M,M,M, M, M,10 },
{M,M,M, 20,M,60 },
{M,M,M, M, M,M }
};
typedef struct edge{
int adjvex;//边的一个顶点
int cost; //权值
}edge;
int total=0; //计数变量，计算共选择节点多少个
int adjvex[6];//保存依次被选中的节点
edge lowpathcost[6];//初始值为矩阵的第一行。
char path[6][10]={"0","","","","",""};//以0为初始节点开始计算最短路径 (路径)
for(int i=1;i<6;i++)
{lowpathcost[i].cost=cost[0][i];//初始化为M，最短路径长度为矩阵的第一行权值
if(cost[0][i]!=M)
{
lowpathcost[i].adjvex=0;//有数据则adjvex置为0
cout<<"初始存在路径的是"<<0<<"----"<<i<<endl;
}
}
int min;//保存最小权值
int minvex;//保存最小权值边的另一顶点
int selected[6]={0};//次变量是作为控制已输出的节点不再参与的判断参数
cout<<endl<<"开始选择顶点："<<endl;
for(int num=1;num<=5;num++) //要选择的次数,共6个顶点,除掉起点
{
min=M;
for(i=1;i<=5;i++)
if(min>lowpathcost[i].cost&&!selected[i])
{
min=lowpathcost[i].cost;//第一次查找为10 即第一行中最小的值
minvex=i;//此时i=2
}
adjvex[++total]=minvex;//此时adjvex[1]为2，存放依次选出的顶点
//adjvex[2]=1
if(min!=M)
{
cout<<"第 "<<num<<" 次被选择的顶点是:" <<minvex<< " . " <<"对应的边上的权值是 "<<min<<endl;
}
selected[minvex]=1; //已参与的节点就置为1
for(i=0;i<6;i++)//这一个循环是算法步骤的第三步，
if(!selected[i] && lowpathcost[i].cost>min+cost[minvex][i] && min+cost[minvex][i]<M)//3项都要满足
{
lowpathcost[i].cost=min+cost[minvex][i];
lowpathcost[i].adjvex=minvex;
}
}
for(i=1;i<=5;i++)
cout<<" "<<lowpathcost[i].adjvex;
cout<<endl<<endl;
int eadjvex,sadjvex;
char ep[2];
for(i=1;i<=total;i++)
{
eadjvex=adjvex[i];
sadjvex=lowpathcost[eadjvex].adjvex;
ep[0]='0'+eadjvex; ep[1]='\0';
char tmp[10];
strcpy(tmp,path[sadjvex]);
strcpy(path[eadjvex],strcat(tmp,ep));// path[e]=sp+ep;
cout<<"0 到顶点 "<<eadjvex <<" 的最短路径经历的节点依次是："<<path[eadjvex]<<" 长度是："<<lowpathcost[eadjvex].cost<<endl;
}
}

4. C语言:int型数组path(迪杰斯特拉算法路径数组)，每个数组存的是它上一个点的脚标i.

这个算法开始时，一般前把path数组初始化为某个值init，然后从起点出发，从j点走到另一个点i，就让path[i] = j，直到i为终点就表示已经找到路径。

因此，这数组可以这么理解，如果path[i]等于j，就表示有一条路是从j到i

所以path[5]是终点，就说明5是终点。

找起点的时候就让一个变量now = 终点，只要path[now]不等于init，就让now = path[now],也就是等于现在的now的之前那个点，path[now]等于init就说明当前点已经是起点。

#include<stdio.h>
intmain()
{
//初始化path数组以及搜索路径
while(path[now]!=init)//当path[now]等于init，表示之前的now已经是起点
{
//这里可以对当前点做一些操作
now=path[now];//让now变成前面那个点
}
//输出起点终点
return0;
}

5. 求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);
}

6. 一道利用迪杰斯特拉算法的C语言题 ，求改错

我忘记改了哪个地方了，你自己跑一下
#include <stdio.h>
#include <string.h>
#define size 12
int i,j,T,D,S;
int map[size][size],vis[size],dist[size];
void vist()
{
memset(vis,0,sizeof(vis));
for(i=0;i<size;i++)
{
for(j=0;j<size;j++)
{
map[i][j]=999999;
}
map[i][i]=0;
dist[i]=999999;
dist[0]=0;
}
}
void dijk()
{
int temps,min;
for(i=0;i<size;i++)
{
temps=0;
min=999999;
for(j=0;j<size;j++)
{
if((!vis[j])&&(dist[j]<min))
{
temps=j;
min=dist[j];
}
}
vis[temps]=1;
for(j=0;j<size;j++)
{
if((!vis[j])&&dist[j]>map[temps][j]+dist[temps])
{
dist[j]=map[temps][j]+dist[temps];
}
}
}
}
int main()
{
int A,B,min,x;
while(scanf("%d%d%d",&T,&S,&D) != EOF)
{
vist();
for(i=1;i<=T;i++)
{
scanf("%d%d%d",&A,&B,&x);
if(x<map[A][B])
{
map[A][B]=x;
map[B][A]=x;
}
}
//for(i=1;i<=D;i++){dist[i]=map[1][i];}
for(i=1;i<=S;i++)
{
scanf("%d",&A);
map[0][A]=map[A][0]=0;
dist[A]=0;
}
dijk();
scanf("%d",&A);
min=dist[A];
for(i=1;i<D;i++)
{
scanf("%d",&A);
if(min > dist[A])
{
min=dist[A];
}
}
printf("%d\n",min);
}
return 0;
}

7. 用Dijkstra算法的基本思路并且是用C语言编写出求最小路径的代码

Dijkstra算法的基本思路是：假设每个点都有一对标号 (dj, pj)，其中dj是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：
1) 初始化。起源点设置为：① ds=0, ps为空;② 所有其他点: di=∞, pi=?;③ 标记起源点s，记k=s,其他所有点设为未标记的。
2) 检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：
dj=min［dj, dk+lkj］
式中，lkj是从点k到j的直接连接距离。
3) 选取下一个点。从所有未标记的结点中，选取dj 中最小的一个i：
di=min［dj, 所有未标记的点j］
点i就被选为最短路径中的一点，并设为已标记的。
4) 找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点,设置：
i=j*
5) 标记点i。如果所有点已标记，则算法完全推出，否则，记k=i，转到2) 再继续。

#include <stdio.h>
#define true 1
#define false 0
#define I 9999 /* 无穷大 */
#define N 20 /* 城市顶点的数目 */

int cost[N][N] = {
{0,3,I,I,I,1,I,I,I,I,I,I,I,I,I,I,I,I,I,I},
{3,0,5,I,I,I,6,I,I,I,I,I,I,I,I,I,I,I,I,I},
{I,5,0,4,I,I,I,1,I,I,I,I,I,I,I,I,I,I,I,I},
{I,I,4,0,2,I,I,I,6,I,I,I,I,I,I,I,I,I,I,I},
{I,I,I,2,0,I,I,I,I,7,I,I,I,I,I,I,I,I,I,I},
{1,I,I,I,I,0,1,I,I,I,2,I,I,I,I,I,I,I,I,I},
{I,6,I,I,I,1,0,6,I,I,I,7,I,I,I,I,I,I,I,I},
{I,I,1,I,I,I,6,0,2,I,I,I,3,I,I,I,I,I,I,I},
{I,I,I,6,I,I,I,2,0,8,I,I,I,4,I,I,I,I,I,I},
{I,I,I,I,7,I,I,I,8,0,I,I,I,I,5,I,I,I,I,I},
{I,I,I,I,I,2,I,I,I,I,0,4,I,I,I,3,I,I,I,I},
{I,I,I,I,I,I,7,I,I,I,4,0,3,I,I,I,4,I,I,I},
{I,I,I,I,I,I,I,3,I,I,I,3,0,3,I,I,I,5,I,I},
{I,I,I,I,I,I,I,I,4,I,I,I,3,0,7,I,I,I,2,I},
{I,I,I,I,I,I,I,I,I,5,I,I,I,7,0,I,I,I,I,3},
{I,I,I,I,I,I,I,I,I,I,3,I,I,I,I,0,5,I,I,I},
{I,I,I,I,I,I,I,I,I,I,I,4,I,I,I,5,0,8,I,I},
{I,I,I,I,I,I,I,I,I,I,I,I,5,I,I,I,8,0,6,I},
{I,I,I,I,I,I,I,I,I,I,I,I,I,2,I,I,I,6,0,4},
{I,I,I,I,I,I,I,I,I,I,I,I,I,I,3,I,I,I,4,0}
};
int dist[N]; /* 存储当前最短路径长度 */
int v0 = 'A' - 65; /* 初始点是 A */

void main()
{
int final[N], i, v, w, min;

/* 初始化最短路径长度数据，所有数据都不是最终数据 */
for (v = 0; v < N; v++) {
final[v] = false;
dist[v] = cost[v0][v];
}

/* 首先选v0到v0的距离一定最短，最终数据 */
final[v0] = true;

/* 寻找另外 N-1 个结点 */
for (i = 0; i < N-1; i++) {
min = I; /* 初始最短长度无穷大 */

/* 寻找最短的边 */
for (w = 0; w < N; w++) {
if (!final[w] && dist[w] < min) {
min = dist[w];
v = w;
}
}
final[v] = true; /* 加入新边 */

for (w = 0; w < N; w++) { /* 更新 dist[] 数据 */
if (!final[w] && dist[v] + cost[v][w] < dist[w]) {
dist[w] = dist[v] + cost[v][w];
}
}
}

for (i = 0; i < N; i++) { /* 显示到监视器 */
printf("%c->%c: %2d\t", v0 + 65, i + 65, dist[i]);
}
}

8. 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]));
}
}
}
}

9. C语言：迪杰斯特拉算法怎么看

下面是一道dijkstra的代码，题目在最下面。
每句解释很详细。

#include <stdio.h>

int a[205][205]; //记录邻接矩阵
int dist[205]; //到每个点的最短路
int m,n; //m条路，n个点

const int INF=0xfffffff;

void init() //初始化各点间距离
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
a[i][j]=(i==j?0:INF);
}

void dijkstra(int u) //从第u个点开始走
{
int sign[205]={0}; //标记走过否
int x=u;
int i,j;

for(i=0;i<n;i++) //初始化u到各点距离
dist[i]=a[x][i];
dist[x]=0;
sign[x]=1;

for(i=1;i<=n-2;i++) //找u到各点距离中的最小值
{
int min=INF;
for(j=0;j<n;j++)
{
if(!sign[j] && min>dist[j])
{
min=dist[j];
x=j;
}
}

sign[x]=1;

for(j=0;j<n;j++) //初始化x到各点间距离
{
if(!sign[j] && dist[x]+a[x][j]<dist[j] && a[x][j]<INF)
dist[j]=a[x][j]+dist[x];
}
}

}

int main()
{
int i;
while(scanf("%d %d",&n,&m)!=EOF)
{
init();
for(i=0;i<m;i++)
{
int x,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;
}
int s,t;
scanf("%d %d",&s,&t);
dijkstra(s);

if(dist[t]<2000000)
printf("%d\n",dist[t]);
else
printf("-1\n");
}
return 0;
}

/*

本题目包含多组数据，请处理到文件结束。
每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000)，分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0～N-1编号。
接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。
再接下一行有两个整数S,T(0<=S,T<N)，分别代表起点和终点。
Sample Input
3 3
0 1 1
0 2 3
1 2 1
0 2

3 1
0 1 1
1 2

Sample Output
2
-1
*/