Dijkstra C++实现

在这里#include
#include
#include
#include
#include



#define Ifo 0x3f3f3f3f //等效无穷大

using namespace std;

int n, m;//图的顶点数、边数
int map[1005][1005];//图表示方法
int dist[1005];//一个顶点到其他所有顶点的最短距离
int path[1005];//最短路径中，当前位置顶点的上一个顶点位置
int vis[1005];//顶点被访问为1，否则为0

ifstream fin;
//初始化图矩阵，所有值为无穷大
void Init()
{
	memset(map, Ifo, sizeof(map));
	for (int i = 1; i <= n; i++)
	{
		map[i][i] = 0;
	}
}
//读取图中所有顶点的边，边的权重，构建图
void Getmap()
{
	int u, v, w;
	fin.open("C:/Users/17926/Desktop/min_dist.txt", ios::in);
	if (!fin)
	{
		cout << "wenjiandakaishibai" << endl;
	}
	string buff;
	while (!fin.eof())
	{
		getline(fin, buff);
		if (!buff.empty())
		{
			u = (int)buff[0] - 48;//char to int
			v = (int)buff[1] - 48;
			w = (int)buff[2] - 48;
			if (map[u][v] > w)
			{
				map[u][v] = w;
			}
		}
	}
	fin.close();
	
	
}

void dijkstra(int vertex)
{
	memset(dist, Ifo, sizeof(dist));//初始化所有距离为无穷大
	memset(path, -1, sizeof(path));//初始化所有路径为-1
	memset(vis, 0, sizeof(path));
	dist[vertex] = 0;
	vector connect_vertexs;//当前访问顶点的所有邻接点
	int min_dist;//未被访问顶点中的最短距离
	int min_dist_vertex;//未被访问顶点中的最短距离所对应的顶点
	while (true)
	{
		min_dist_vertex = 0;
		min_dist = Ifo;
		for (int i = 1; i <= n; i++)
		{
			if (vis[i] == 0)
			{
				if (min_dist > dist[i])
				{
					min_dist = dist[i];
					min_dist_vertex = i;
				}
			}
		}
		if (min_dist_vertex == 0) break;//没有找到合适的顶点

		vis[min_dist_vertex] = 1;

		for (int j = 1; j <= n; j++)
		{
			if (map[min_dist_vertex][j] > 0 && map[min_dist_vertex][j] < Ifo)
				connect_vertexs.push_back(j);
		}
		for (auto& v : connect_vertexs)
		{
			if (vis[v] == 0 && (dist[min_dist_vertex] + map[min_dist_vertex][v]) < dist[v])
			{
				dist[v] = dist[min_dist_vertex] + map[min_dist_vertex][v];
				path[v] = min_dist_vertex;
			}
		}

		connect_vertexs.clear();
		if (connect_vertexs.empty())
		{
			cout << "connect_vertexs is empty!" << endl;
		}
	}
}


int main()
{
	cout << "输入顶点数、边数：";
	cin >> n >> m;
	clock_t start = clock();
	Init();
	Getmap();
	dijkstra(1);
	clock_t end = clock();
	cout << "cost time:" << (end - start)*1000 / CLOCKS_PER_SEC << "ms" << endl;
	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= n; j++)
		{
			cout << map[i][j] << " ";
		}
		cout << endl;
	}

	cout << "dist:";
	for (int i = 1; i <= n; i++)
	{
		cout << dist[i] << ',';
	}
	cout << endl;

	cout << "path:";
	for (int i = 1; i <= n; i++)
	{
		cout << path[i] << ',';
	}
	cout << endl;

	return 0;
}插入代码片