データ構造総括14——図5——単一ソース最短パスby DexterYan

一、基礎知識
二、コード要求
隣接マトリクス、隣接テーブルのいずれかを図の記憶構造として選択し、ディジェストラアルゴリズムを用いて、指定された単一ソース点から図中の残りの各頂点への最短経路(2時間)を実現する.
三、アルゴリズムの構想分析
四、アルゴリズムの反省
五、コード実現

#include
#include
#define MaxVertexNum 100
#define INF 32767   //INF     
typedef char VertexType;
typedef int EdgeType;

typedef struct
{
	VertexType vexs[MaxVertexNum];//   
	EdgeType edges[MaxVertexNum][MaxVertexNum];//  ，     
	int n,e;//       
}MGraph;//          

struct node
{
	int adjvex;
	int lowcost;		//        
}closedge[MaxVertexNum];//      ，   U U-V         （U        ） 

int visited[MaxVertexNum];

int CreateMGraph(MGraph *G)//         
{
	int i, j, k, weight;
	printf("         （     ：   ，  ）：
");
	scanf("%d,%d",&(G->n),&(G->e));//        				/* G->n           ？*/
	printf("       （     ：   ）：
");
	for(i=0; in; i++)
	{
		scanf("
%c",&(G->vexs[i]));//      ，    
	}
	for(i=0; in; i++)
	{
		for(j=0; jn; j++)
		{
			G->edges[i][j]=INF;//        
		}
	}
	printf("                      （     ：i,j,weight）：
");
	for(k=0; ke; k++)
	{
		scanf("%d,%d,%d",&i,&j,&weight);
		G->edges[i][j]=weight;//     G->deges[j][i]=1,               
	//	G->edges[j][i]=weight;
	}
	/*        ，         
	for(i=0; in; i++)
	{
		for(j=0; jn; j++)
		{
			printf("(%d)",G->edges[i][j]);
		}
		printf("
");
	}
	*/
}

void dispath(int dist[],int path[],int s[],int n,int v)
{
	int i,k;
	for(i=0; in; i++)
	{
		dist[i]=G->edges[v][i];//      
		s[i]=0;					//s     ，0          
		if(G->edges[v][i]n; i++)//  ，    v             
	{
		mindis=INF;
		k=v;
		for(j=0; jn; j++)// V-S            vk 
		{
			if(s[j]==0&&dist[j]n; j++)//  V-S      dist[j] 
		{
			if(s[j]==0&&G->edges[k][j]edges[k][j]edges[k][j];
				path[j]=k;
			}
		}
	}
	dist[v]=0; 
	dispath(dist,path,s,G->n,v);//       
}

int main()
{
	MGraph x;
	int start;
	CreateMGraph(&x);
	printf("       ：");
	scanf("%d",&start); 
	dijkstra(&x,start);
	return 0;
}

六、コードの反省
脳障害バグ1、scanfの中には他の文字はありません.例えばscanf(「開始頂点:%dを入力してください」、&start);これにより、文字を表示しないだけでなく、付与のプロセスにも影響します.