dijkstra.cpp

关于数据结构 图的实验 源码及运行结果的说明

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

struct VillageGraph
{
	int vexnum;
	int arcs[30][30];
}g;

int dijkstra(VillageGraph g,int v0);	//返回从V0到最远结点的最短距离

int main()
{
	//从文件“input.txt”中读入带权无向图信息
	string path;
	int i,j,min,minv;
	ifstream infile("input.txt");
	if (infile.is_open()) cout<<"图文件打开成功"<<endl;
	else {cout<<"文件打开失败，程序异常终止。"<<endl; return 0;}
	infile>>g.vexnum;
	for (i=0;i<g.vexnum;i++)
		for (j=0;j<g.vexnum;j++)
			infile>>g.arcs[i][j];
	min=-1;
	minv=-1;
	for (i=0;i<g.vexnum;i++)
	{
		j=dijkstra(g,i);
		cout<<"如果选择v"<<i<<"建医院，到最远村子的最短距离是"<<j<<endl;
		if ((min==-1)||(j<min)) {min=j; minv=i;}
	}
	cout<<"最适合建医院的村子是v"<<minv<<endl;
	return 0;
}

int dijkstra(VillageGraph g,int v0)
{
	const MAX_INT=10000000;		//最远距离
	int *d;			//数组D存放V0到其他节点的已知最短路径
	bool *s;		//集合S为已求得最短路径的顶点
	int v1;			//从V0出发最短路径的当前结点,临时量
	d=new int[g.vexnum];
	s=new bool[g.vexnum];
	int i,j;
	for (i=0;i<g.vexnum;i++) 
	{
		d[i]=MAX_INT;	//初始化d数组
		s[i]=false;			//初始化S数组
	}
	s[v0]=true;	//初始化环境
	d[v0]=0;	//默认V0到自己的距离是0
	v1=v0;
	for (i=0;i<g.vexnum-1;i++)		//dijkstra主循环开始
	{
		//更新d数组
		for (j=0;j<g.vexnum;j++)
			if ((s[j]==false)&&(g.arcs[v1][j]))
				if (d[v1]+g.arcs[v1][j]<d[j])
					d[j]=d[v1]+g.arcs[v1][j];
		//找到当前d中最短路径顶点，将其加入S集合
		v1=-1;
		for (j=0;j<g.vexnum;j++)
			if ((s[j]==false)&&((v1==-1)||(d[j]<d[v1]))) v1=j;
		s[v1]=true;
		//test cout
		cout<<v0<<"->"<<v1<<", 最短路径="<<d[v1]<<endl;
	}
	return d[v1];
}