有权图单源最短路径Dijkstra算法和多源最短路径Floyd算法

样例：

1.Dijkstra算法

#include <iostream>
#include <stack>
#define inf 1000000
#define MaxVertex 100
using namespace std;
typedef int Vertex;
typedef class MatrixGraph* MGraph;
class MatrixGraph
{
public:

	void Build(MGraph Graph);
	void Create(MGraph Graph,Vertex s);
	Vertex FindMin(MGraph Graph,Vertex s);
	void Dijkstra(MGraph Graph,Vertex s);
	void Output(MGraph Graph,Vertex s);
private:
	int G[MaxVertex][MaxVertex];//矩阵从1开始存储
	int dist[MaxVertex];//距离
	int path[MaxVertex];//路径
	bool collected[MaxVertex];//收录集合
	int Nv;//顶点
	int Ne;//边
};


//初始化
void MatrixGraph::Build(MGraph Graph)
{
	Vertex v1, v2;
	int weight;
	//初始化图
	cout << "输入顶点数：";
	cin >> Graph->Nv;
	for (int i = 1; i <= Graph->Nv; i++)
		for (int j = 1; j <= Graph->Nv; j++)
			Graph->G[i][j] = 0;
	//初始化距离
	for (int i = 0; i <=Graph->Nv; i++)
		Graph->dist[i] = inf;//初始化无穷大
	//初始化路径
	for (int i = 1; i <= Graph->Nv; i++)
		Graph->path[i] = -1;
	//初始化收录情况
	for (int i = 1; i <= Graph->Nv; i++)
		Graph->collected[i] = false;
	//初始化点
	cout << "输入边数：";
	cin >> Graph->Ne;
	cout << "输入边<v1,v2>和相应权重："<<endl;
	for (int i = 1; i <= Graph->Ne; i++)
	{
		cin >> v1 >> v2 >> weight;
		Graph->G[v1][v2] = weight;//有向图
	}
}
//建立并初始化顶点、邻接点信息
void MatrixGraph::Create(MGraph Graph,Vertex s)
{
	Graph->dist[s] = 0;
	Graph->collected[s] = true;//已收录
	for (int i = 1; i <= Graph->Nv; i++)
	{
		if (Graph->G[s][i])//<s,i>存在边
		{
			Graph->dist[i] = Graph->G[s][i];//i的距离等于权重
			Graph->path[i] = s;//i要经过s;
		}
	}
}
//查找当前未收录顶点中最短路径,返回该顶点
Vertex MatrixGraph::FindMin(MGraph Graph,Vertex s)
{
	Vertex min;
	min = 0;//初始化的时候是从0开始使dist[0]无穷大
	for (Vertex v=1; v <= Graph->Nv; v++)
	{
		if (v!=s&&!Graph->collected[v]&&Graph->dist[v]<Graph->dist[min])
		{
			min = v;
		}
	}
	return min;
}
//迪杰斯特拉算法
void MatrixGraph::Dijkstra(MGraph Graph,Vertex s)
{
		Create(Graph, s);
		while (1)
		{
			Vertex v = FindMin(Graph, s);//找到
			if (!v)//如果V返回值为0，跳出循环
				break;
			Graph->collected[v] = true;//收录
			for (Vertex w = 1; w <= Graph->Nv; w++)
			{
				if (!Graph->collected[w] && Graph->G[v][w])//如果当前顶点未收录且为邻接点
				{
					if (Graph->dist[v] + Graph->G[v][w] < Graph->dist[w])//说明w路径要通过v
					{
						Graph->dist[w] = Graph->dist[v] + Graph->G[v][w];//w的最短路径
						Graph->path[w] = v;	//w经过v
					}
				}
			}
		}
}
//输出
void MatrixGraph::Output(MGraph Graph,Vertex s)
{
	int i, j, k,d;
	stack<Vertex> S;
	for (i = 1; i <= Graph->Nv; i++)
	{
		cout << "终点："<<i<<" ";
		//输出到终点最短距离
		cout << "最短路径：";
		j = i;
		d = 0;
		while (j)
		{
			d += Graph->dist[j];
			j--;
		}
		cout << d<<" ";
		//输出经过路径
		cout << "过程：";
		k = i;
		bool flag = false;
		do {
			S.push(k);
			k = Graph->path[k];

		} while (k != -1);
		while (!S.empty())
		{
			if (!flag)
			{
				cout << S.top();
				flag = true;
			}
			else
				cout << "->" << S.top();
			S.pop();
		}
		cout << endl;
	}
}
int main()
{
	int s;
	MatrixGraph MG;
	MGraph Graph = new MatrixGraph;;
	MG.Build(Graph);
	cout << "输入起始顶点：";
	cin >> s;
	MG.Dijkstra(Graph, s);
	MG.Output(Graph,s);
	return 0;
}
	

运行：

2.Floyd算法

#include<iostream>
#define INF 1000000//无穷大
#define MaxVertex 20
typedef int Vertex;
typedef class MatrixGraph* MGraph;
using namespace std;

class MatrixGraph
{
public:
	void Build(MGraph Graph);
	void Floyd(MGraph Graph);
	void Output(MGraph Graph);
private:
	int Nv;
	int Ne;
	int G[MaxVertex][MaxVertex];
	int path[MaxVertex][MaxVertex];//路径
	int dist[MaxVertex][MaxVertex];//距离
};
//初始化，从1下标开始
void MatrixGraph::Build(MGraph Graph)
{
	Vertex v1, v2;
	int weight;
	cout << "输入顶点数：";
	cin >> Graph->Nv;
	//初始化图的值为无穷大
	for (int i = 1; i <= Graph->Nv; i++)
		for (int j = 1; j <= Graph->Nv; j++)
			Graph->G[i][j] = INF;
	cout << "输入边数：";
	cin >> Graph->Ne;
	//初始化点
	cout << "输入边<v1,v2>和相应权重：" << endl;
	for (int i = 1; i <= Graph->Ne; i++)
	{
		cin >> v1 >> v2 >> weight;
		Graph->G[v1][v2] = weight;//有向边
	}
}
//弗洛伊德
void MatrixGraph::Floyd(MGraph Graph)
{
	//初始化路径和距离
	for(Vertex i=1;i<=Graph->Nv;i++)
		for (Vertex j = 1; j <= Graph->Nv; j++)
		{
			Graph->dist[i][j] = Graph->G[i][j];
			Graph->path[i][j] = -1;
		}
	//遍历矩阵找出两点最短路径
	for(Vertex k=1;k<=Graph->Nv;k++)
		for(Vertex i=1;i<=Graph->Nv;i++)
			for (Vertex j = 1; j <= Graph->Nv; j++)
			{
				if (Graph->dist[i][k] + Graph->dist[k][j] < Graph->dist[i][j])
				{
					Graph->dist[i][j] = Graph->dist[i][k] + Graph->dist[k][j];//更新最短路径长度
					Graph->path[i][j] = k;//更新最短路径
				}
			}
}
//输出
void MatrixGraph::Output(MGraph Graph)
{
	Vertex v, w;
	int print[MaxVertex];//记录路径输出情况(这里用bool会中断)
	while (1)
	{
		cout << "输入1-"<<Graph->Nv<<"任意两个顶点(0 0退出)：";
		cin >> v >> w;
		if (v == 0 && w == 0)
			break;
		if (Graph->dist[v][w]==INF||v<1||v>Graph->Nv||w<1||w>Graph->Nv)
		{
			cout << "从" << v << "到" << w << "路径不存在" << endl;
			continue;
		}
		cout << "从" << v << "到" << w << "之间最短路径长度：" << Graph->dist[v][w] << " ";
		for (int i = 1; i <= Graph->Nv; i++)
				print[i] = false;//初始化未输出
		cout << "路径：";
		if (v < w)
			for (int i=v; i < w; i++)
			{
				if (!print[Graph->path[v][i + 1]])
				{
					if (!print[v])
					{
						if (Graph->path[v][i + 1] == -1)
						{
							print[Graph->path[v][i + 1]] = true;
							cout << v;
						}
						else
							cout << v;

						print[v] = true;
					}
					if (!print[Graph->path[v][i + 1]])
					{
						cout << "->" << Graph->path[v][i + 1];
						print[Graph->path[v][i + 1]] = true;
					}
				}
			}
		else
			for (int i=v; i > w; i--)
			{
				if (!print[Graph->path[v][i - 1]])
				{
					if (!print[v])
					{
						if (Graph->path[v][i - 1] == -1)
						{
							print[Graph->path[v][i - 1]] = true;
							cout << v;
						}
						else
							cout << v;
						print[v] = true;
					}
					if (!print[Graph->path[v][i - 1]])
					{
						cout << "->" << Graph->path[v][i - 1];
						print[Graph->path[v][i - 1]] = true;
					}
				}
			}
		if(!print[w])
			cout << "->" << w;
		cout << endl;
	}
}
int main()
{
	MatrixGraph MG;
	MGraph Graph = new MatrixGraph;
	MG.Build(Graph);
	MG.Floyd(Graph);
	MG.Output(Graph);
	return 0;
}

运行：