蓝桥杯 最短路问题 dijkstra算法负权值计算

原题如下:
试题 算法训练 最短路

资源限制
时间限制:1.0s 内存限制:256.0MB
问题描述
给定一个n个顶点,m条边的有向图(其中某些边权可能为负,但保证没有负环)。请你计算从1号点到其他点的最短路(顶点从1到n编号)。

输入格式
第一行两个整数n, m。

接下来的m行,每行有三个整数u, v, l,表示u到v有一条长度为l的边。

输出格式
共n-1行,第i行表示1号点到i+1号点的最短路。
样例输入
3 3
1 2 -1
2 3 -1
3 1 2
样例输出
-1
-2
数据规模与约定
对于10%的数据,n = 2,m = 2。

对于30%的数据,n <= 5,m <= 10。

对于100%的数据,1 <= n <= 20000,1 <= m <= 200000,-10000 <= l <= 10000,保证从任意顶点都能到达其他所有顶点。

思路分析

很多人看到这题之后认为不能使用dijstra算法,原因是题目中包含负权值,但其实这题也是可以使用dijistra算法的,因为题目中已经说明了,不包含负环,其实就是一个隐含条件,暗示我们可以使用dijkstra算法。

首先,简单介绍一下dijkstra算法不能计算负环的原因。
dijkstra算法本身是基于贪心算法的逻辑,每一次都基于现有路径条件计算到某一起点的最短值。但是负权值一旦出现,算法逻辑就不再成立了。

因为目的是得到最短路径,而在负环中,最短路径是负无穷大,从我们的常规认识上来说就已经出现了问题。

当然从算法角度上来说,真正的问题是,因为负环的出现,导致算法不能保证每一步找到的路径就是当前节点的最短路径,贪心算法的查找也就失去了意义。

所以这题,从条件上看好像可以使用djikstra算法。

但是,需要考虑到的是,djikstra的时间复杂度为(N^2),而节点的数量可以达到20000个。也就是说超时的可能性非常大,实际运行中也证实了我的猜想。

两个节点为20000的数据没能通过……

但是,你以为我在这里就结束了嘛?不?我不能止步于此。

我尝试性的小小删改了djikstra的贪心查找部分,结果很轻易的拿到了满分,这是我没想到的。因为从逻辑上来说,如果不基于贪心来查找的话,对付复杂的环状图是容易出现问题的。因为节点的确定的最短路径可能一直变化(贪心查找时确定之后是不变的)。

原因分析:可能是测试数据用的图不参杂环状图,或者是简单的环状图

下面是修改后的代码:

 #include <iostream>
#include <stdio.h>
using namespace std;

int n, m,ma;

class l
{
public:
	int v, d;
	l *next;
	void init (int a=-1, int b=0)
	{
		v = a;
		d = b;
		next = NULL;
	}
};
l map [20005];
l* p;

class vertex
{
public:
	int b;
	int d;
	vertex(int a=200000)
	{
		b = 0;
		d = a;
	}
};
vertex v[20005];

void shortestroute()
{
	for (int i = 1; i < n; i++)
	{
		p = &map[0];
		while (p != NULL)
		{
			if (p->v ==i)
			{
				v[i].d = p->d;
			}
			p = p->next;
		}
	}
	ma = 200000;
	for (int i = 1; i < n;)
	{
		for (int j = 1; j < n; j++)
		{
			if (v[j].b == 0 && v[j].d < ma)
			{
				i+=1;

				v[j].b = 1;
				p = &map[j];
				while (p != NULL)
				{
					if (p->d + v[j].d < v[p->v].d)
					{
						v[p->v].d = p->d + v[j].d;
					}
					p = p->next;
				}
			}
		}
	}
	for (int i = 1; i < n; i++)
	{	
			cout << v[i].d<<endl;
	}
}

int main()
{
	int a,b,c;
	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		scanf("%d%d%d", &a, &b, &c);
		if(map[a-1].d==0)
			map[a-1].init(b-1, c);
		else
		{
			p = new l;
			p->init(b-1, c);
			p->next = map[a-1].next;
			map[a-1].next = p;
		}
	}

	shortestroute();

	return 0;
}

上一篇:最短路径算法总结


下一篇:Dijkstra算法—栅格地图最短路径