問題描述
將圖以鄰接矩陣或鄰接表存儲，實現(xiàn)Dijkstra算法。

算法設(shè)計
迪杰斯特拉算法：

1.假設(shè)用帶權(quán)的鄰接矩陣arc，來表示帶權(quán)有向圖，arc[i][j]，表示弧<vi,vj>上的權(quán)值。若<vi,vj>不存在，則置arc[i][j]為無窮。
S為已找到從v出發(fā)的最短路徑的終點的集合，它的初始狀態(tài)為空集。那么，從v出發(fā)到圖上其余各頂點可能達(dá)到的最短路徑長度的初值為:
D[j]=arcs[LocateVex(G,v)][i] vi∈V

2.選擇vj，使得 D[j]=Min{D[i]|vi∈V-S}
vj就是當(dāng)前求得的一條從v出發(fā)的最短路徑的終點。令S=S∪{j}

3.修改從v出發(fā)到集合V-S上任一頂點vk可達(dá)的最短路徑長度。如果
D[j]+arcs[j][k]<D[k] 則修改D[k]為D[k]=D[j]+arcs[j][k]

4.重復(fù)操作2，3共n-1次。
由此求得從v到圖上其余各頂點的最短路徑是依路徑長度遞增的序列。

#include<stdio.h> #include<string.h> #define INF 32767 #define MAXVEX 30 int dist[MAXVEX]; //建立dist數(shù)組int path[MAXVEX]; //建立path數(shù)組int S[MAXVEX]; //建立S數(shù)組typedef char VertexType;typedef struct graph {int n,e;VertexType vexs[MAXVEX];int edges[MAXVEX][MAXVEX]; }MGraph;void CreateMGraph(MGraph &G) {int n,e;int value;char temp_i;char temp_j;printf("請輸入圖的頂點數(shù)和邊數(shù)（以空格分隔）：");scanf("%d%d",&n,&e);G.n=n;G.e=e;for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(i==j)G.edges[i][j]=0;elseG.edges[i][j]=32767;}}printf("輸入頂點信息：");for(int j=0;j<G.n;j++){getchar();scanf("%c",&G.vexs[j]);}int temp_number_i;int temp_number_j;printf("請輸入每條邊的權(quán)值：\n");for(int j=0;j<e;j++){getchar();scanf("%c %c %d",&temp_i,&temp_j,&value);for(int i=0;i<n;i++){if(G.vexs[i]==temp_i)temp_number_i=i;if(G.vexs[i]==temp_j)temp_number_j=i;}G.edges[temp_number_i][temp_number_j]=value;}}void DispMGraph(MGraph &G) {printf("輸出頂點信息：\n");for(int i=0;i<G.n;i++){printf("%c",G.vexs[i]);} printf("\n輸出鄰接矩陣：\n");printf("\t");for(int i=0;i<G.n;i++)printf("%8c",G.vexs[i]); for(int i=0;i<G.n;i++){printf("\n%8c",G.vexs[i]);for(int j=0;j<G.n;j++){if(G.edges[i][j]==32767) //兩點之間無連接時權(quán)值為默認(rèn)的32767，// 在無向圖中一般用"0"表示，在有向圖中一般用"∞",// 這里為了方便統(tǒng)一輸出 "∞"printf("%8s", "∞");elseprintf("%8d",G.edges[i][j]);}printf("\n");} }void Dijkstra(MGraph g, int v) { //求從v到其他頂點的最短路徑int mindis,i,j,u=0;for (i=0;i<g.n;i++){ dist[i]=g.edges[v][i]; //距離初始化S[i]=0; //S[]置空if (g.edges[v][i]<INF) //路徑初始化path[i]=v; //v→i有邊時，置i前一頂點為velse //v→i沒邊時，置i前一頂點為-1path[i]=-1;}S[v]=1; //源點編號v放入S中for (i=0;i<g.n-1;i++) //循環(huán)向S中添加n-1個頂點{ mindis=INF; //mindis置最小長度初值for (j=0;j<g.n;j++) //選取不在S中且有最小距離頂點uif (S[j]==0 && dist[j]<mindis) { u=j;mindis=dist[j];}S[u]=1; //頂點u加入S中for (j=0;j<g.n;j++) //修改不在s中的頂點的距離if (S[j]==0)if (g.edges[u][j]<INF&& dist[u]+g.edges[u][j]<dist[j]){ dist[j]=dist[u]+g.edges[u][j];path[j]=u;}} }void Print(MGraph G,int v) {printf("\n");for(int i=0;i<G.n;i++){if(i!=v && dist[i]!=INF){printf("%c到%c的最短距離為：%d\n",G.vexs[v],G.vexs[i],dist[i]);}else if(dist[i]==INF){printf("%c與%c之間無路徑！\n",G.vexs[v],G.vexs[i]); } }printf("\n"); }/*------------------輸出從頂點v出發(fā)的所有最短路徑-------------------*/ static void Dispath(MGraph g, int v) {int i, j, k;int apath[MAXVEX], d; //存放一條最短路徑(逆向)及其頂點個數(shù)//循環(huán)輸出從頂點v到i的路徑for(i = 0; i < g.n; i++){if(S[i] == 1 && i != v){printf("從頂點%c到頂點%c的路徑長度為:%d\t路徑為:", g.vexs[v], g.vexs[i], dist[i]);d = 0; apath[d] = i; //添加路徑上的終點k = path[i];if(k == -1) //沒有路徑的情況printf("無路徑\n");else //存在路徑時輸出該路徑{while(k != v){d++;apath[d] = k;k = path[k];}d++; apath[d] = v; //添加路徑上的起點printf("%c ", g.vexs[apath[d]]); //先輸出起點for(j = d - 1; j >= 0; j--) //再輸出其余頂點printf(" %c ", g.vexs[apath[j]]);printf("\n");}}} }int main() {MGraph G;CreateMGraph(G);DispMGraph(G);Dijkstra(G,0);Print(G,0);Dispath(G,0); }

總結(jié)

以上是生活随笔為你收集整理的数据结构——图-迪杰斯特拉算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。