13週目のオンサイト実践-プロジェクト1(3)-Dijkstraアルゴリズムの検証、1つの頂点から残りの各頂点への最短パス
8816 ワード
/*
*Copyright(c) 2015,
*All rights reserved.
* :test.cpp
* :
* :2015 11 27
* :v1.0
*
* :Dijkstra , ;
* :
* : 。
*/
1.ヘッダファイル:graph.h、図データ構造を定義するコード、マクロ定義、アルゴリズムを実現する関数の宣言を含む.
#ifndef GRAPH_H_INCLUDED
#define GRAPH_H_INCLUDED
#define MAXV 100 //
#define INF 32767 //INF ∞
typedef int InfoType;
//
typedef struct
{
int no; //
InfoType info; // ,
} VertexType; //
typedef struct //
{
int edges[MAXV][MAXV]; //
int n,e; // ,
VertexType vexs[MAXV]; //
} MGraph; //
//
typedef struct ANode //
{
int adjvex; //
struct ANode *nextarc; //
InfoType info; // ,
} ArcNode;
typedef int Vertex;
typedef struct Vnode //
{
Vertex data; //
int count; // ,
ArcNode *firstarc; //
} VNode;
typedef VNode AdjList[MAXV]; //AdjList
typedef struct
{
AdjList adjlist; //
int n,e; // n e
} ALGraph; //
// : ,
// :Arr - , , Arr ( int )
// n -
// g -
void ArrayToMat(int *Arr, int n, MGraph &g); //
void ArrayToList(int *Arr, int n, ALGraph *&); //
void MatToList(MGraph g,ALGraph *&G);// g G
void ListToMat(ALGraph *G,MGraph &g);// G g
void DispMat(MGraph g);// g
void DispAdj(ALGraph *G);// G
#endif // GRAPH_H_INCLUDED
2.ソースファイル:graph.cpp,各種アルゴリズムを実現する関数の定義を含む
#include <stdio.h>
#include <malloc.h>
#include "graph.h"
// : ,
// :Arr - , , Arr ( int )
// n -
// g -
void ArrayToMat(int *Arr, int n, MGraph &g)
{
int i,j,count=0; //count , 0
g.n=n;
for (i=0; i<g.n; i++)
for (j=0; j<g.n; j++)
{
g.edges[i][j]=Arr[i*n+j]; // Arr n×n ,Arr[i*n+j] Arr[i][j],
if(g.edges[i][j]!=0 && g.edges[i][j]!=INF)
count++;
}
g.e=count;
}
void ArrayToList(int *Arr, int n, ALGraph *&G)
{
int i,j,count=0; //count , 0
ArcNode *p;
G=(ALGraph *)malloc(sizeof(ALGraph));
G->n=n;
for (i=0; i<n; i++) //
G->adjlist[i].firstarc=NULL;
for (i=0; i<n; i++) //
for (j=n-1; j>=0; j--)
if (Arr[i*n+j]!=0) // , Arr n×n ,Arr[i*n+j] Arr[i][j]
{
p=(ArcNode *)malloc(sizeof(ArcNode)); // *p
p->adjvex=j;
p->info=Arr[i*n+j];
p->nextarc=G->adjlist[i].firstarc; // *p
G->adjlist[i].firstarc=p;
}
G->e=count;
}
void MatToList(MGraph g, ALGraph *&G)
// g G
{
int i,j;
ArcNode *p;
G=(ALGraph *)malloc(sizeof(ALGraph));
for (i=0; i<g.n; i++) //
G->adjlist[i].firstarc=NULL;
for (i=0; i<g.n; i++) //
for (j=g.n-1; j>=0; j--)
if (g.edges[i][j]!=0) //
{
p=(ArcNode *)malloc(sizeof(ArcNode)); // *p
p->adjvex=j;
p->info=g.edges[i][j];
p->nextarc=G->adjlist[i].firstarc; // *p
G->adjlist[i].firstarc=p;
}
G->n=g.n;
G->e=g.e;
}
void ListToMat(ALGraph *G,MGraph &g)
// G g
{
int i,j;
ArcNode *p;
g.n=G->n; // “ ” 。g.n ,
g.e=G->e;
for (i=0; i<g.n; i++) //
for (j=0; j<g.n; j++)
g.edges[i][j]=0;
for (i=0; i<G->n; i++) // ,
{
p=G->adjlist[i].firstarc;
while (p!=NULL)
{
g.edges[i][p->adjvex]=p->info;
p=p->nextarc;
}
}
}
void DispMat(MGraph g)
// g
{
int i,j;
for (i=0; i<g.n; i++)
{
for (j=0; j<g.n; j++)
if (g.edges[i][j]==INF)
printf("%3s","∞");
else
printf("%3d",g.edges[i][j]);
printf("
");
}
}
void DispAdj(ALGraph *G)
// G
{
int i;
ArcNode *p;
for (i=0; i<G->n; i++)
{
p=G->adjlist[i].firstarc;
printf("%3d: ",i);
while (p!=NULL)
{
printf("-->%d/%d ",p->adjvex,p->info);
p=p->nextarc;
}
printf("
");
}
}
3.テスト関数:main.cpp、関連テストを完了します.
#include <stdio.h>
#include <malloc.h>
#include "graph.h"
#define MaxSize 100
void Ppath(int path[],int i,int v) //
{
int k;
k=path[i];
if (k==v) return; //
Ppath(path,k,v); // k
printf("%d,",k); // k
}
void Dispath(int dist[],int path[],int s[],int n,int v)
{
int i;
for (i=0; i<n; i++)
if (s[i]==1)
{
printf(" %d %d :%d\t :",v,i,dist[i]);
printf("%d,",v); //
Ppath(path,i,v); //
printf("%d
",i); //
}
else printf(" %d %d
",v,i);
}
void Dijkstra(MGraph g,int v)
{
int dist[MAXV],path[MAXV];
int s[MAXV];
int mindis,i,j,u;
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;
else
path[i]=-1;
}
s[v]=1;
path[v]=0; // v s
for (i=0; i<g.n; i++) //
{
mindis=INF; //mindis
for (j=0; j<g.n; j++) // s u
if (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;
}
}
Dispath(dist,path,s,g.n,v); //
}
int main()
{
MGraph g;
int A[7][7]=
{
{0,4,6,6,INF,INF,INF},
{INF,0,1,INF,7,INF,INF},
{INF,INF,0,INF,6,4,INF},
{INF,INF,2,0,INF,5,INF},
{INF,INF,INF,INF,0,INF,6},
{INF,INF,INF,INF,1,0,8},
{INF,INF,INF,INF,INF,INF,0}
};
ArrayToMat(A[0], 7, g);
Dijkstra(g,0);
return 0;
}
実行結果: