c語言dijkstra演算法

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

Ⅱ 用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演算法 利用C語言計算最短路徑出現的問題~

dijkstra(Time,maxnod伏散,m,n);
改為燃廳雀
Dijkstra(Time,maxnod皮早,m,n);

Ⅳ 求高手修改下dijkstra最短路演算法c語言源代碼~~運行出1 error(s), 0 warning(s)

Dijkstra算冊蠢法--c++源代碼--by 偉偉豬 [轉貼 2005-12-15 20:21:00 ] 發表者: 偉偉豬

/***********************************************
設G=(V,E)是一個每條邊都有非負長度的有向圖，有一個特異的頂點s稱為緣。
單源最短路徑問題，或者稱為最短路徑問題，是要確定從s到V中沒一個其他
頂點的距離，這里從頂點s到x的距離定義為從s到x的最短路徑問題。拿姿桐這個問題
可以用Dijkstra演算法解決。下面我給我了c++下的源代碼！ --by 偉偉豬
************************************************/
#include<iostream.h>
void main()
{
int infinity=100,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++)
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]<infinity) p[i]=0;
else p[i]=-1;
}

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

}
cout<<"從源點到其它頂點的最短距離依次如下：";
for(i=1;i<n;i++) cout<<d[i]<<" ";

}
/*********
頂點個數用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頁
************/

Ⅳ dijkstra演算法求該源頂點到其它所有頂點的最短路徑和最短路徑長度,並輸出。用無向網鄰接表存儲結構。C語言

#include<stdio.h>
#define N 100
#define MaxDist 10000
int mapdist[N][N];
int mindist[N];
void Dijkstra(int n,int c)
{
int i,tag[N],minc,t,j;
for(i=1;i<=n;++i)
{
if(mapdist[c][i]>=0)
mindist[i]=mapdist[c][i];
else
mindist[i]=MaxDist;
tag[i]=0;
}
for(j=1;j<=n;++j)
{
minc=MaxDist;
for(i=1;i<=n;++i)
{
if(minc>mindist[i])
{
minc=mindist[i];
t=i;
}
}
tag[t]=1;
for(i=1;i<=n;++i)
{
if((mindist[i]>mindist[t]+mapdist[t][i])&&(!tag[i]))
mindist[i]=mindist[t]+mapdist[t][i];

}
}

}
int main()
{
int i,j,n,c;
scanf("%d%d",&n,&c);//c為棚薯源點
for(i=1;i<=n;++i)
{
for(j=1;j<=n;++j)
scanf("%d",&mapdist[i][j]);//-1表逗和薯示山者不直接連通
}
Dijkstra(n,c);
for(i=1;i<=n;++i)
printf("%d",mindist[i]);
return 0;
}

Ⅵ 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演算法輸出inf 。。。為什麼。。。求高手解讀。。。

找了半天沒找出來，但我有另一種方法：
需要調用C語言函數DIJK（給出）。將其放散簡入MATLAB工作文件夾下即可。您的則纖方法時間復雜度肯定很高，我用的dijkstra演算法時間復雜度低，是前輩留下的財產，呵呵
n=12;
a=ones(n)+10000;
for i=1:n
a(i,i)=0;
end
a(1,2)=5;
a(2,3)=8;
a(2,6)=5;
a(3,4)=3;
a(3,9)=10;
a(4,5)=5;
a(4,7)=3;
a(5,6)=2;
a(7,8)=2;
a(8,9)=4;
a(8,11)=6;
a(9,10)=3;
a(10,11)=5;
a(10,12)=3;
a=DIJK(a);

函數名為DIJK.C
#include "mex.h"
#include "iostream.h"
#include "stdlib.h"
#include "stdio.h"
#define INFINITY 10000
void dijkstra(double *g,int u1 ,int u2,double *out,double *value,int mrows,int ncols)
{double *p,*d,*final;
int i,v,min,j,w,count,judge=1;
p=(double *)malloc(sizeof(double)*mrows*ncols);
d=(double *)malloc(sizeof(double)*mrows);
final=(double *)malloc(sizeof(double)*mrows);
for(i=0;i<ncols;i++)
{if(*(g+u1-1+i*mrows)==INFINITY)
judge=0;
else {judge=1;break;}
}
if(judge==1){
for(v=0;v<mrows;++v)
{*(final+v)=0;*(d+v)=*(g+u1-1+v*mrows);
for(w=0;w<mrows;++w)
*(p+v+w*mrows)=0;
*(p+v+v*mrows)=1;
if(*(d+v)<INFINITY)
{*(p+v+(u1-1)*mrows)=1;}
}
*(d+u1-1)=0;*(final+u1-1)=1;
for(i=0;i<mrows-1;++i)
{min=INFINITY;
for(w=0;w<mrows;++w)
if(!*(final+w))
if(*(d+w)<min)
{v=w;min=*(d+w);}
*(final+v)=1;
for(w=0;w<mrows;++w)
if((!*(final+w))&&(min+*(g+v+mrows*w)<*(d+w)))
{*(d+w)=min+*(g+v+mrows*w);
for(j=0;j<沖盯褲mrows;++j)
if(*(p+v+j*mrows)==1)
*(p+w+j*mrows)=1;
*(p+w+v*mrows)=1;
}
}
count=0;*out=u1;
for(j=0;j<mrows;++j)
if(*(p+u2-1+j*mrows)==1)
{count=count+1;
if(((j+1)!=u1)&&((j+1)!=u2)) *(out+count)=j+1;
else count=count-1;
}
if(*(d+u2-1)!=INFINITY)
*value=*(d+u2-1);
else *value=0;
if(*value!=0) *(out+count+1)=u2;
}
else{
for(j=0;j<mrows;++j)
*(out+j)=0;
*value=0;
}
free(p);free(d);free(final);
}
void mexFunction(int nlhs,mxArray *plhs[],int nrhs,const mxArray *prhs[])
{double *out,*value;
double *g;
int u1,u2;
int mrows,ncols;
u1=mxGetScalar(prhs[1]);
u2=mxGetScalar(prhs[2]);
g=mxGetPr(prhs[0]);
mrows=mxGetM(prhs[0]);
ncols=mxGetN(prhs[0]);
plhs[0]=mxCreateDoubleMatrix(1,ncols,mxREAL);
plhs[1]=mxCreateDoubleMatrix(1,1,mxREAL);
out=mxGetPr(plhs[0]);
value=mxGetPr(plhs[1]);
dijkstra(g,u1,u2,out,value,mrows,ncols);
}

Ⅷ 怎麼用c語言實現單源最短路徑問題要求是用Dijkstra演算法，最好寫出所有的代碼 ，包括結構定義等等，對一

C語言代碼：//清華大學出版社光碟的代碼
void ShortestPath_DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D)
{ // 演算法7.15
// 用Dijkstra演算法求有向網G的v0頂點到其餘頂點v的最短路徑P[v]
// 及其帶權長度D[v]。
// 若P[v][w]為TRUE，則w是衡辯嘩灶賀從v0到v當前求得最短路徑上的頂點。
// final[v]為TRUE當且僅當v∈S,即已經求得從v0到v的最短路徑。
int i=0,j, v,w,min;
bool final[MAX_VERTEX_NUM];
for (v=0; v<G.vexnum; ++v) {
final[v] = FALSE;
D[v] = G.arcs[v0][v].adj;
for (w=0; w<G.vexnum; ++w) P[v][w] = FALSE; // 設空路徑
if (D[v] < INFINITY) { P[v][v0] = TRUE; P[v][v] = TRUE; }
}
D[v0] = 0; final[v0] = TRUE; // 初始化，v0頂點屬於S集
//--- 開始主循環，每次求得v0到某個v頂點的最短路徑，並加v到S集 ---
for (i=1; i<G.vexnum; ++i) { // 其餘G.vexnum-1個頂點
min = INFINITY; // 當前所知離v0頂點的最近距離
for (w=0; w<G.vexnum; ++w)
if (!final[w]) // w頂點在V-S中
if (D[w]<min) { v = w; min = D[w]; } // w頂點離v0頂點更近
final[v] = TRUE; // 離v0頂點最近的咐行v加入S集
for (w=0; w<G.vexnum; ++w) // 更新當前最短路徑及距離
if (!final[w] && (min+G.arcs[v][w].adj<D[w])) {
// 修改D[w]和P[w], w∈V-S
D[w] = min + G.arcs[v][w].adj;
for(j=0;j<G.vexnum;j++) P[w][j] = P[v][j]; //第v行賦值於第w行
P[w][w] = TRUE; // P[w] = P[v]+[w]
}//if
}//for
} // ShortestPath_DIJ

Ⅸ c語言 在用廣度優先演算法求最短路徑時候，怎麼樣能記錄它的路徑

路徑
template<class Type>
void Dijkstra(int n, int v, Type dist[], int prev[], Type **c) {
//單源最短路徑問題的 Dijkstra 演算法
bool s[maxint];
for (int i = 1; i <= n; i++) {
dist[i] = c[v][i];
s[i] = false;
if (dist[i] == maxint) prev[i] = 0;
else prev[i] = v;
}
dist[v] = 0; s[v] = true;
for (int i = 1; i < n; i++) {
int temp = maxint;
int u = v;
for (int j = 1; j <= n; j++)
if (!s[j] && dist[j] < temp) {
u = j;
temp = dist[j];
}
s[u] = true;
for (int j = 1; j <= n; j++)
if (!s[j] && c[i][j] < maxint) {
Type newdist = dist[u] + c[u][j];
if (newdist < dist[j]) {
dist[j] = newint;
prev[j] = u;
}
}
}
}
另外,站長團上有產品團購,便宜有保證