shortestpathofgraph.cpp

关于数据结构的各章节的c原代码实现

// shortestpathofgraph.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#define  MAX 1000
	int path[7][7];
	int dist[7];
	int distp2p[7][7];
void creategraph(int *node,int n)
{  int from,to;
   for (int i=0;i<n;i++)
   {
	from=node[3*i];
	to=node[3*i+1];
    path[from][to]=node[3*i+2];
   }
}
void creategraphp2p(int *node,int n)
{
   int from,to;
   for (int i=0;i<n;i++)
   {
	   from=node[3*i];
	   to=node[3*i+1];
	   path[from][to]=node[3*i+2];
	   path[to][from]=node[3*i+2];
   }
}
void shortestp2p(int num)
{
   for(int i=1;i<num;i++)
	   for(int j=1;j<num;j++)
		   if(i!=j)distp2p[i][j]=path[i][j];
		   else distp2p[i][j]=0;
		   for(int k=1;k<num;k++)
			   for(int i=1;i<num;i++)
	              for(int j=1;j<num;j++)
					  if(distp2p[i][k]+distp2p[k][j]<distp2p[i][j])
						  distp2p[i][j]=distp2p[i][k]+distp2p[k][j];
}
void shortestpath(int begin,int num)
{
int selected[7];
int min;
int s;
for (int i=2;i<=num;i++)
{
	dist[i]=path[begin][i];
	selected[i]=0;
}
selected[begin]=1;
dist[begin]=0;
printf("顶点 1     2     3     4     5     6\n");
for(i=1;i<=num;i++)printf("%6d",dist[i]);
printf("\n");
for (i=1;i<num;i++)
{
  min=MAX;
  for(int j=1;j<=num;j++)
  {
  if(dist[j]<min&&selected[j]==0)
  {
	  min=dist[j];
      s=j;
  }
  }
  selected[s]=1;
 for (j=1;j<=num;j++)
 {
	 if(selected[j]==0&&dist[s]+path[s][j]<dist[j])
		 dist[j]=dist[s]+path[s][j];
	  printf("%6d",dist[j]);
 }
 printf("\n");
}
}
int main(int argc, char* argv[])
{   
	int node[7][3]={{1,2,35},{2,3,45},{2,4,30},{3,5,25},{4,5,45},{4,6,130},{5,6,100}};


	for(int i=1;i<7;i++)
	  for (int j=1;j<7;j++)
	  {
		  path[i][j]=MAX;
	  }
	//creategraph(node[0],7);
	creategraphp2p(node[0],7);
	printf("加权图的邻接矩阵内容：\n");
	for(i=1;i<7;i++)
	{
		for (int j=1;j<7;j++)
			printf("%6d",path[i][j]);
		printf("\n");
	}	  
 //printf("\n从顶点1到各顶点最近距离计算过程：\n");
 //shortestpath(1,6);
 printf("\n从各顶点到各顶点最近距离计算过程：\n");
 shortestp2p(7);
 printf("顶点 1     2     3     4     5     6\n");
 for(i=1;i<=6;i++)
	{ for(int j=1;j<=6;j++)
     printf("%6d",distp2p[i][j]);
     printf("\n");
 }
	return 0;
}