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