abc.txt

C++实现最小生成树和最短路径

#include<iostream>
#include "string.h"
#include<iomanip>
using namespace std;
#define vex_num 20
#define vertex_max 20
#define maxint 2000

typedef char vextype[20];
typedef struct
{
	vextype vexs[vertex_max];
	int arcs[vertex_max][vertex_max];
	int vexnum,arcnum;
}mgraph;
int n,m;
void creat_mgraph(mgraph *g)
{
	int i,j,k;
	int w;
	cout<<"请输入顶点数和边数";
	cin>>n>>m;
	g->vexnum=n;
	g->arcnum=m;
	cout<<"请输入顶点信息";
	for(i=0;i<n;i++)
	{
		cin>>g->vexs[i];
	}
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			g->arcs[i][j]=maxint;
		cout<<"请输入两个顶点的边和权值(i,j,w)"<<endl;
		for(k=0;k<m;k++)
		{
			cin>>i>>j>>w;
			g->arcs[i][j]=w;
		}
		
	
}
void dijkstra(mgraph gn,int v0,int path[],int dist[])
{
	int i,j;int k=v0;
	int v,w,min;
	int s[vex_num];
	for(v=0;v<n;v++)
	{
		s[v]=0;
		dist[v]=gn.arcs[v0][v];
		if(dist[v]<maxint)
			path[v]=v0;
		else 
			path[v]=-1;
	}
	dist[v0]=0;
		s[v0]=1;
		for(i=1;i<n;i++)
		{
			min=maxint;
			for(w=0;w<n;w++)
			{if(!s[w]&&dist[w]<min)
				{
					k=w;
					min=dist[w];}}
					s[k]=1;
					for(j=0;j<n;j++)
						if(!s[j]&&(min+gn.arcs[k][j]<dist[j]))
						{
							dist[j]=min+gn.arcs[k][j];
							path[j]=k;
						}
				
		}
	
}
void putpath(mgraph g,int v0,int i,int p[],int d[])
{
	
	int next;
	
		if(p[i]!=-1 && i!=v0)
		{
			cout<<g.vexs[i]<<"<--";
			next=p[i];
			while(next!=v0)
			{
				cout<<g.vexs[next]<<"<--";
				next=p[next];
			}
			cout<<g.vexs[v0]<<':'<<d[i]<<"     "<<endl;
		}
		else 
			if(p[i]==-1&&i!=v0)
				cout<<g.vexs[i]<<"<--"<<g.vexs[v0]
				<<"    没有路径存在"<<endl;
}
void main()
{  
	int i;
    int v0,c;
    vextype vinfo,abc;
    int path[vex_num];
	int dist[vex_num];
    mgraph g;
    creat_mgraph(&g);

    cout<<"请输入起始点和终点 :"; 
    cin>>vinfo>>abc;
    for(i=0;i<n;i++)
	{if(strcmp(vinfo,g.vexs[i])==0)
        v0=i;
	if(strcmp(abc,g.vexs[i])==0)
        c=i;}
    dijkstra(g,v0,path,dist);
    putpath(g,v0,c,path,dist);
}