c++来写一个求最短路径算法的程序

本文来讲解一下用c++来设计一个关于最短路径的程序。

1.首先把图片中的各个景点(地方)绘制成一个无向带权图。

2.将图中的景点绘制成无向带权图为：Q——R = 7（补充）

以上用A,B,C,D…来代替以上20个地方。

3.用弗洛伊德拉算法来实现两点间最短路径查找：
（1）.先把数据按 顶点 顶点 权值 （A B 8 表示A和B之间的路径大小为8）储存在一个名为"data.txt"文档中方便读取。(若不直接相连则权值为99，意为无穷大)

（2）.然后按格式读取文件数据内容，构建一个邻接带权矩阵

//找出顶点对应的下标
int find_position(char arg)
{
	for(int K=0;K<vertexNum;K++)
	{
		if(vertex[K] == arg)
			return K;
	}
};

void read_data()
{
	char first,last;
	int firstNumber,lastNumber,weight;
	string line;
	ifstream file("data.txt");//打开文件
	while(!file.eof())
	{
		getline(file,line);
		if(line.size()==5)//5代表权值是小于10
		{
			first = line[0];
			last = line[2];
			weight = line[4]-48;//用ASCII码值来转换
		}
		else
		{
			first = line[0];
			last = line[2];
			weight = (line[4]-48)*10+(line[5]-48);//用ASCII码值来转换
		}
		firstNumber = find_position(first);
		lastNumber = find_position(last);
		edge[firstNumber][lastNumber] = weight;//更新权值
	}
}

（3）.构建完邻接矩阵之后，用弗洛伊德算法把算出一个最后路径权值矩阵 和 路径矩阵

void Floyd()
{
	int i,j,k,dist[20][20];
    string path[20][20];
    for(i=0;i<20;i++)
        for(j=0;j<20;j++)
    {
        dist[i][j]=edge[i][j];
        if(dist[i][j]!=99 && dist[i][j]!=0)
        {
        	//不能直接相加，字符直接相加会转换为ASCII码相加后得到另一个字符
            //path[i][j] = vertex[i]+vertex[j];
            path[i][j] = vertex[i];
            path[i][j] = path[i][j]+vertex[j];
        }
		//若为99或0则为空
        else
            path[i][j]="";
    }

    for(k=0;k<20;k++)
        for(i=0;i<20;i++)
            for(j=0;j<20;j++)
    {
        if(dist[i][k] + dist[k][j] < dist[i][j])
        {
            dist[i][j]=dist[i][k] + dist[k][j];
            path[i][j]=path[i][k] + path[k][j];
        }

    }
}

（4）.经过以上步骤，得到的dist二维数组和path二维数据已经储存了完了整个图的信息包括最短权值和路径，接下来读取用户输入的起点和终点。

首先先对上面的几个函数整合一下得到一下代码

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
using namespace std;
int vertexNum=20;
char vertex[20] = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T'};
int edge[20][20];
int i,j,k,dist[20][20];
string path[20][20];

//定义查找对应顶点的数组下标
int find_position(char arg)
{
	for(i=0;i<vertexNum;i++)
	{
		if(vertex[i] == arg)
			return i;
	}
};

//定义读取数组函数
void read_data()
{
	char first,last;
	int firstNumber,lastNumber,weight;
	string line;
	ifstream file("data.txt");//打开文件
	while(!file.eof())
	{
		getline(file,line);
		if(line.size()==5)//5代表权值是小于10
		{
			first = line[0];
			last = line[2];
			weight = line[4]-48;//用ASCII码值来转换
		}
		else
		{
			first = line[0];
			last = line[2];
			weight = (line[4]-48)*10+(line[5]-48);//用ASCII码值来转换
		}
		firstNumber = find_position(first);
		lastNumber = find_position(last);
		edge[firstNumber][lastNumber] = weight;//更新权值
	}
}

//定义核心算法
void Floyd()
{
    for(i=0;i<20;i++)
        for(j=0;j<20;j++)
    {
        dist[i][j]=edge[i][j];
        if(dist[i][j]!=99 && dist[i][j]!=0)
        {
        	//不能直接相加，字符直接相加会转换为ASCII码相加后得到另一个字符
            //path[i][j] = vertex[i]+vertex[j];
            path[i][j] = vertex[i];
            path[i][j] = path[i][j]+vertex[j];
        }
		//若为99或0则为空
        else
            path[i][j]="";
    }

    for(k=0;k<20;k++)
        for(i=0;i<20;i++)
            for(j=0;j<20;j++)
    {
        if(dist[i][k] + dist[k][j] < dist[i][j])
        {
            dist[i][j]=dist[i][k] + dist[k][j];
            path[i][j]=path[i][k] + path[k][j];
        }

    }
}

int main()
{
    //打开文件读取数据
    read_data();
    Floyd();
	//验证查看一下输出是否正确
    for(i=0;i<20;i++)
    {
        for(j=0;j<20;j++)
        {
            printf("%2d,",dist[i][j]);
        }
        cout<<endl;
    }
    for(i=0;i<20;i++)
    {
        for(j=0;j<20;j++)
        {
            cout<<path[i][j]<<"\t";
        }
        cout<<endl;
    }

    return 0;
}

！！！注意到paht数组里面会重复，所以转换的时候要注意
然后再加入一个while循环对用户输入的起始顶点和终止顶点进行转换输出。

void output()
{
	string name[vertexNum]={"正门","软件学院","广场","图书馆","行政楼","信息中心","教学楼","篮球场","运动场","体育馆","商业街","餐厅","学生活动中心","停车场","学生宿舍区1","教室公寓","学生宿舍区2","25号楼","招待所","北门",};
	char first,last;
	int firstNumber,lastNumber;
	while(true)
	{
		cout<<"请输入起点(用A B C ...表示):";
		cin>>first;
		cout<<"请输入终点(用A B C ...表示):";
		cin>>last;
		firstNumber = find_position(first);
		lastNumber = find_position(last);
		//利用path中储存的字符串来转换输出
		transform(path[firstNumber][lastNumber]);
		cout<<"继续查找请输入1，否则请输入0:";
		cin>>k;
		if(k==0)
			break;
	}
}
void transform(string road)
{
	int length = road.size();//判断数组长度
	string way = road;
	cout<<length<<endl;
	i = 0;
	cout<<road<<endl;
	while(true)//隔两个
	{
			j = find_position(way[i]);
			cout<<name[j]<<"-->";
			i=i+2;
			if(i>=length)
                break;
	}
	j = find_position(way[length-1]);
    cout<<name[j];
}

最后，贴一段完整可执行代码

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
using namespace std;
int vertexNum=20;
string name[20]={"正门","软件学院","广场","图书馆","行政楼","信息中心","教学楼","篮球场","运动场","体育馆","商业街","餐厅","学生活动中心","停车场","学生宿舍区1","教室公寓","学生宿舍区2","25号楼","招待所","北门",};
char vertex[20] = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T'};
int edge[20][20];
int i,j,k,dist[20][20];
string path[20][20];

//定义查找对应顶点的数组下标
int find_position(char arg)
{
	for(K=0;K<vertexNum;K++)
	{
		if(vertex[K] == arg)
			return K;
	}
};

//定义读取数组函数
void read_data()
{
	char first,last;
	int firstNumber,lastNumber,weight;
	string line;
	ifstream file("data.txt");//打开文件
	while(!file.eof())
	{
		getline(file,line);
		if(line.size()==5)//5代表权值是小于10
		{
			first = line[0];
			last = line[2];
			weight = line[4]-48;//用ASCII码值来转换
		}
		else
		{
			first = line[0];
			last = line[2];
			weight = (line[4]-48)*10+(line[5]-48);//用ASCII码值来转换
		}
		firstNumber = find_position(first);
		lastNumber = find_position(last);
		edge[firstNumber][lastNumber] = weight;//更新权值
	}
}

//定义核心算法
void Floyd()
{
    for(i=0;i<20;i++)
        for(j=0;j<20;j++)
    {
        dist[i][j]=edge[i][j];
        if(dist[i][j]!=99 && dist[i][j]!=0)
        {
        	//不能直接相加，字符直接相加会转换为ASCII码相加后得到另一个字符
            //path[i][j] = vertex[i]+vertex[j];
            path[i][j] = vertex[i];
            path[i][j] = path[i][j]+vertex[j];
        }
		//若为99或0则为空
        else
            path[i][j]="";
    }

    for(k=0;k<20;k++)
        for(i=0;i<20;i++)
            for(j=0;j<20;j++)
    {
        if(dist[i][k] + dist[k][j] < dist[i][j])
        {
            dist[i][j]=dist[i][k] + dist[k][j];
            path[i][j]=path[i][k] + path[k][j];
        }

    }
}

void transform(string road)
{
	int length = road.size();//判断数组长度
	string way = road;
	cout<<length<<endl;
	i = 0;
	cout<<road<<endl;
	while(true)//隔两个
	{
			j = find_position(way[i]);
			cout<<name[j]<<"-->";
			i=i+2;
			if(i>=length)
                break;
	}
	j = find_position(way[length-1]);
    cout<<name[j];
}

void output()
{

	char first,last;
	int firstNumber,lastNumber;
	while(true)
	{
		cout<<"请输入起点(用A B C ...表示):";
		cin>>first;
		cout<<"请输入终点(用A B C ...表示):";
		cin>>last;
		firstNumber = find_position(first);
		lastNumber = find_position(last);
		//利用path中储存的字符串来转换输出
		transform(path[firstNumber][lastNumber]);
		cout<<endl;
		cout<<"继续查找请输入1，否则请输入0:";
		cin>>k;
		if(k==0)
			break;
	}
}


int main()
{
    //打开文件读取数据
    read_data();
    Floyd();
    output();
return 0;
}

以上仅仅是个人尝试，有一点小错误，但不影响，并不是最优解，第一发博客，望见谅。

data数据在:data数据