图的操作与实现

/ 2评论 / 393阅读 / 0点赞

要求


源代码

若以下显示需要登录,请刷新页面或点击此处下载。


思考

若只求带权有向图G中从顶点i到顶点j的最短路径,如何修改Dijkstra 算法来实现这一功能?

void Dijkstra_way(int first_point)
{
	int* widget_list = new int[map_size];	//记录距离0的长度
	for (int i = map_size; i--;)
	{
		widget_list[i] = INF;
		adjList[i].weight = -1;
	}
	widget_list[first_point] = 0;
	adjList[first_point].weight = 0;
	for (int i = 1; i < map_size; ++i)
		for (int j = map_size; j--;)		//计算距离
			if (adjList[j].weight >= 0)
				for (node* node_p = adjList[j].next_p; node_p != NULL; node_p = node_p->next_p)
					if (widget_list[j] + node_p->weight < widget_list[node_p->data])
					{
						widget_list[node_p->data] = widget_list[j] + node_p->weight;
						adjList[node_p->data].weight = j;
					}
	cout << "<< Dijkstra 最短路径:" << endl;
	coolQueue<int> stack;
	for (int i = 0; i < map_size; ++i)
	{
		for (int j = i; j != first_point;)
		{
			stack.End_push(j);
			j = adjList[j].weight;
		}
		cout << "<< " << first_point;
		for (int pop_int = 0; stack.End_pop(pop_int);)
			cout << " -> " << pop_int;
		cout << endl;
		stack.clear();
	}
	adjList_reflush();
}
  1. Clollag说道:

    She spent her whole life taking care of her family cialis for sale Joel Topf, MD, is a partner at St

  2. Best rating of https://top-gambling-programs.com/ affiliate programs in casino and sports betting, Great affiliate programs only with us, review, rating

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注