?? dijkstra.c
字號:
/* 標準文檔模板 */
#include "Stdio.h"
#include "Conio.h"
#define N 5 /*N為結點總數*/
int main(void)
{
int dis[N]; int path[N]; int k=0,i,mark,max,a,j;int b[N];
int q[100];int z; int M[N][N];
FILE *fp;
fp=fopen("data.txt","r");
for(i=0;i<N;i++)
for(j=0;j<N;j++)
{fscanf(fp,"%d",&M[i][j]);}
fclose(fp);
for(i=0;i<N;i++) /*設定k源點,path,dis的初值*/
{ if(i!=k) M[i][i]=0; /*k為源點*/
else M[i][i]=1;
dis[i]=M[k][i]; /*源點到個頂點路徑長度*/
if(dis[i]<32767) path[i]=k;
else path[i]=0;
}
for(i=0;i<N-1;i++) /*確定源點到各頂點路徑,除源點外要處理N-2條路徑*/
{ mark=k; max=32767;
for(a=0;a<N;a++) /*在未處理的頂點中,確定當前路徑中最短路徑*/
{ if(M[a][a]==0&&dis[a]<max)
{max=dis[a];mark=a;}
}
/* printf("mark=%d",mark);printf("\n"); */
/*mark,max中記錄路徑最短的結點下標和長度*/
/*所有結點處理完畢,結束*/
M[mark][mark]=1; /*將選中頂點送入w集合中*/
for(j=0;j<N;j++) /*利用頂點mark調整dis中路徑長度*/
{ if(M[j][j]==0&&M[mark][j]<32767&&dis[mark]+M[mark][j]<dis[j])
{dis[j]=dis[mark]+M[mark][j]; /* printf("dis[%d]=%d ",j,dis[j]);printf("\n"); */
path[j]=mark; /*調整j結點的直接前驅*/
}
}
}
for(i=0;i<N;i++)
{if(i==k||dis[i]==0)continue;
printf("%d-%d: ",k,i);
q[0]=path[i];
j=0;
while(q[j]!=k)
{j++;
q[j]=path[q[j-1]];
}
for(z=j;z>=0;z--)
{ printf("%d-",q[z]);
}printf("%d",i); printf(" "); printf("dis=%d",dis[i]); printf("\n");
}
getch();
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -