迪傑斯特拉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
*/