博客

最短路(poj1502 poj3259 poj1125)

  • Post author:
  • Post category:其他


1 . Dijkstra算法


适用范围：1、单源最短路径；2、有向&无向图

/* 
poj 1502
Dijkstra + 邻接表
time : 16ms
memory : 436k
复杂度：O(|E|+|V|^2) 若图是稠密的，算法基本是最优的，若图是稀疏的，则扫描一遍Dist数组花费O(|V|^2)就显得太慢。
可以用最小堆存储各节点最小距离，利用最小堆的性质依次让距离最小的节点出堆，可简化代码时间。不过如何使用堆暂时还未想到。

代码依据《数据结构与算法分析》编写。
*/

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

typedef int Vertex;

#define NotAVertex -1
#define Max 101
#define INF 100000

struct ListEntry
{
    struct ListEntry *Next;
    Vertex id;
    int Dist;
};

typedef ListEntry* List;

struct TableEntry
{
    List Header;
    int Known;
    int Dist;
    Vertex Path;
};

typedef TableEntry Table[Max];

void InitTable(Vertex Start, Table T, int NumVertex)
{
    int i, j;
    List list1, list2;
    char Dist[10];
    for(i = NumVertex; i > 0; --i)
    {
        T[i].Known = 0;
        T[i].Path = NotAVertex;
        T[i].Dist = INF;
        T[i].Header = new ListEntry[1];
        T[i].Header -> Next = NULL;
    }
    T[Start].Dist = 0;

    for(i = 2; i <= NumVertex; ++i)
    {
        for(j = 1; j < i; ++j)
        {
            scanf("%s", Dist);
            if(Dist[0] != 'x')
            {
                list1 = new ListEntry[1];
                list1 -> Dist = atoi(Dist);
                list1 -> id = j;
                list1 -> Next = T[i].Header -> Next;
                T[i].Header -> Next = list1;

                list2 = new ListEntry[1];
                list2 -> Dist = atoi(Dist);
                list2 -> id = i;
                list2 -> Next = T[j].Header -> Next;
                T[j].Header -> Next = list2;
            }
        }
    }
}

void Dijkstra(Table T, int Num)
{
    Vertex V;
    int j, min;
    List list;

    while(1)
    {
        min = INF;  
        for(j = 1; j <= Num; ++j)
        {      
            if(!T[j].Known && T[j].Dist < min)
            {  
                min = T[j].Dist;  
                V = j;  
            }  
        }
        if(min == INF)
            break;

        T[V].Known = 1;

        list = T[V].Header;
        while(list -> Next)
        {
            list = list -> Next;
            if(!T[list -> id].Known)
            {
                if(T[V].Dist + list -> Dist < T[list -> id].Dist)
                {
                    T[list -> id].Dist = T[V].Dist + list -> Dist;
                    T[list -> id].Path = V;
                }
            }
        }
    }
}

int main()
{
    int Num, ans = -1;
    Table T;
    cin >> Num;
    InitTable(1, T, Num);
    Dijkstra(T, Num);
    for(int i = 2; i <= Num; i++)  
    {
        if(T[i].Dist > ans) 
            ans = T[i].Dist;
    }
    printf("%d\n",ans); 
    return 0;
}


PS：Dijkstra算法路径长度可以用二维数组（稠密时较好）存储(

见贰圣的文章

)，但一般在图稀疏时多用邻接表。若图为无向图，二维数组矩阵以对角线对称，而邻接表则要为一条边的两个点的邻接表都存储一次。有向图正常存储即可。




2 . Bellman-Ford算法

以上的Dijkstra法只适用于无负权值的情况下，一旦图中有负值，算法可能有错，下面将使用Bellman-Ford算法，该算法适用于有负值的图，但若图中有负环路，则无解。



该解法将数据存储在边的结构体中，包含起点，终点，路径权值。这种表示方法是有向的，但是对于无向图可以将此边使用两次，即起点与终点可以互换使用。适用范围：1、单源最短路径；2、有向&无向图；3、边权可正可负（负环路要有错误提示）；4、差分约束系统（不懂o(╯□╰)o）


详细算法分析见：Tanky Woo的文章
 

/*
poj1502
Bellman-Ford算法相比Dijkstra算法较慢。 
time : 16ms
memory : 200k
算法复杂度为: O(|E|*|V|)
*/
#include <stdio.h>
#include <iostream>
using namespace std;

#define MaxNode 100
#define MaxEdge 10000
#define INF 1000000

struct Edge
{
    int s, e, d;
};

Edge edge[MaxEdge]; 
int Dist[MaxNode];
int NumEdge;

void Init(int Num)
{
    int i, j, k = 0;
    char dist[10];

    for(i = 1; i <= Num; ++i)
        Dist[i] = INF;
    Dist[1] = 0;

    for(i = 2; i <= Num; ++i)
    {   
        for(j = 1; j < i; ++j)
        {
            scanf("%s", dist);
            if(dist[0] != 'x')
            {                               //无向图只用存储一次，与Dijkstra不一样，在使用时距离可使用两次
                edge[++k].s = i;
                edge[k].e = j;
                edge[k].d = atoi(dist);
            }
        }
    }
    NumEdge = k;

}

bool Bellman_Ford(int Num)
{
    bool flag = 1;
    for(int i = 0; i < Num - 1; ++i) //循环次数为 节点数-1
    {
        for(int j = 1; j <= NumEdge; ++j)              //对每条边的两个顶点分别进行收缩，一条边的数据使用了两次
        {
            if(Dist[edge[j].e] > Dist[edge[j].s] + edge[j].d)   
                Dist[edge[j].e] = Dist[edge[j].s] + edge[j].d;
            if(Dist[edge[j].s] > Dist[edge[j].e] + edge[j].d)
                Dist[edge[j].s] = Dist[edge[j].e] + edge[j].d;
        }                                          
    }

    for(int k = 1; k < NumEdge; ++k)                //同理，此处判断两次
    {
        if(Dist[edge[k].e] > Dist[edge[k].s] + edge[k].d)
        {
            flag = 0;
            break;
        }
        if(Dist[edge[k].s] > Dist[edge[k].e] + edge[k].d)
        {
            flag = 0;
            break;
        }
    }
    return flag;
}

int main()
{
    int Num, min = -1, i;
    scanf("%d", &Num);
    Init(Num);
    if(Bellman_Ford(Num))
    {
        for(i = 1; i <= Num; ++i)
        {
            if(Dist[i] > min)
                min = Dist[i];
        }
    }
    printf("%d\n", min);
    return 0;
}

3 . SPFA算法




该算法是Bellman-Ford算法的一种

队列实现

，减少了不必要的冗余计算。适用范围与Bellman-Ford算法一致。

详见Tanky Woo的文章

.

这里我用该算法实现  poj 3259 ，此处使用STL里的queue，并且没有使用LLL，SLF等优化队列。该题两点之间不止一条路径，这种情况下应该使用邻接表的方案。
 
/*
poj 3259
SPFA
time: 141ms
memory:240k
*/
#include <stdio.h>
#include <queue>
#include <iostream>
using namespace std;

#define MaxEdge 5210				//注意有2500条路可能为双向，故要乘以2.
#define MaxNode 510
#define INF 1000000

int HeadList[MaxNode];				//存放链表头
int Inqueue[MaxNode];				//判断节点是否在队列里
int Dist[MaxNode];
int cnt[MaxNode];				//每个节点入队次数，当大于等于节点数时，说明有负环

struct EdgeEntry
{
	int s, e, w, next;	
};

EdgeEntry Edge[MaxEdge];

void Init(int N, int M, int W)
{
	int i, j = 1;
	int start, end, weight;
	for(i = 1; i <= N; ++i)			//初始化，特别注意
	{
		HeadList[i] = -1;
		Inqueue[i] = 0;
		Dist[i] = INF;
		cnt[i] = 0;
	}
	cnt[1] = 1;
	Inqueue[1] = 1;
	Dist[1] = 0;

	for(i = 1; i <= M; ++i)
	{
		scanf("%d%d%d", &start, &end, &weight);
		Edge[j].s = start;
		Edge[j].e = end;
		Edge[j].w = weight;
		Edge[j].next = HeadList[start];		//新添加边放在表头
		HeadList[start] = j++;

		Edge[j].s = end;
		Edge[j].e = start;
		Edge[j].w = weight;
		Edge[j].next = HeadList[end];
		HeadList[end] = j++;
	}
	
	for(i = 1; i <= W; ++i)
	{
		scanf("%d%d%d", &start, &end, &weight);
		Edge[j].s = start;
		Edge[j].e = end;
		Edge[j].w = -weight;
		Edge[j].next = HeadList[start];
		HeadList[start] = j++;
	}
}

bool SPFA(int N)
{
	int i, j;
	queue <int>Q;
	Q.push(1);
	
	while(!Q.empty())
	{
		i = Q.front();
		Q.pop();
		Inqueue[i] = 0;

		for(j = HeadList[i]; j != -1; j = Edge[j].next)
		{
			if(Dist[i] + Edge[j].w < Dist[Edge[j].e])
			{
				Dist[Edge[j].e] = Dist[i] + Edge[j].w;
				if(!Inqueue[Edge[j].e])
				{
					Inqueue[Edge[j].e] = 1;
					if(++cnt[Edge[j].e] >= N)
						return true;
					Q.push(Edge[j].e);
				}
			}
		}
		
	}
	return false;
}

int main()
{	
	int N, M, W;
	int Num;
	bool flag;
	scanf("%d", &Num);
	while(Num--)
	{
		scanf("%d%d%d", &N, &M, &W);
		Init(N, M, W);
		flag = SPFA(N);
		if(flag)
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}



4. Floyd算法








以上三种算法一次只能计算单源的最短距离，而Floyd算法适用于多源最短距离计算，支持有向&无向，支持负权。此算法最大的优点是容易理解，代码十分简单。由于三重循环结构紧凑，对于稠密图，效率高于|V|次的Dijkstra算法与|V|次的SPFA算法。k在最外层是出于DP算法。路径的的回溯通过两种方案实现,分为两个版本.

算法复杂度：O(|V|^3)
 
//poj 1125
#include <stdio.h>
#include <iostream>
using namespace std;

#define MaxNode 100
#define INF 1000000
#define max(a,b) a>b?a:b

int Path[MaxNode][MaxNode];		//存储中间节点，用来回溯路径
int Dist[MaxNode][MaxNode];		//初始化为各顶点间直接距离，最后存储各顶点间的最短路径	
int MaxDist[MaxNode];			

void Init(int Num)
{
	int i, j, num, dist;
	for(i = 1; i <= Num; ++i)
		for(j = 1; j <= Num; ++j)
		{
			if(i == j)
				Dist[i][j] = 0;
			else
				Dist[i][j] = INF;
			
			Path[i][j] = -1;<span>		</span>//Path初始化,注意不同的路径回溯对应不同的初始化
		}
	
	for(i = 1; i <= Num; ++i)
	{
		scanf("%d", &num);
		while(num--)
		{
			scanf("%d%d", &j, &dist);
			Dist[i][j] = dist;
		}
	}
}

void Floyd(int Num)
{
	int i, j, k;
	for(k = 1; k <= Num; ++k)
		for(i = 1; i <= Num; ++i)
			for(j = 1; j <= Num; ++j)
			{
				if(Dist[i][k] + Dist[k][j] < Dist[i][j])
				{
					Dist[i][j] = Dist[i][k] + Dist[k][j];
					Path[i][j] = k;		//此处对应不同的路径回溯算法(法一)
				}
			}
}


void Ppath(int i,int j)		//路径回溯算法
{
	int k;
	k = Path[i][j];
	if (k == -1)		//-1意味着直达径最短
		return;
	Ppath(i, k);
	printf("%d ---> ", k);
	Ppath(k, j);
}

int main()
{
	int Num, i, j, maxdist, ans, id;
	while(1)
	{
		scanf("%d", &Num);
		if(!Num)
			break;
		Init(Num);
		Floyd(Num);
		for(i = 1; i <= Num; ++i)
		{
			maxdist  = 0;
			for(j = 1; j <= Num; ++j)
				maxdist = max(maxdist, Dist[i][j]);	
			MaxDist[i] = maxdist;
		}

		ans = INF;
		for(i = 1; i <= Num; ++i)
		{
			if(MaxDist[i] < ans)
			{
				ans = MaxDist[i];
				id = i;
			}
		}

		if(ans != INF)
			printf("%d %d\n", id, ans);
		else
			printf("disjoint\n");
		/*
		此部分为路径回溯部分（测试用）
		for(i = 1; i <= Num; ++i)
			printf("%d %d %d %d %d %d %d %d %d\n", Path[i][1], Path[i][2], Path[i][3], Path[i][4], Path[i][5], Path[i][6], Path[i][7], Path[i][8], Path[i][9]);
		
		i = 3;
		j = 9;
		printf("From %d to %d : ", i, j);
		printf("%d ---> ", i);
		Ppath(i, j);
		printf("%d   ", j);
		printf("Distance: %d  \n", Dist[i][j]);
		*/
	}

	return 0;
}











   



   



    法二:

    

     详见

    
   




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

#define MaxNode 100
#define INF 1000000
#define max(a,b) a>b?a:b

int Path[MaxNode][MaxNode];		//存储中间节点，用来回溯路径
int Dist[MaxNode][MaxNode];		//初始化为各顶点间直接距离，最后存储各顶点间的最短路径	
int MaxDist[MaxNode];			

void Init(int Num)
{
	int i, j, num, dist;
	for(i = 1; i <= Num; ++i)
		for(j = 1; j <= Num; ++j)
		{
			if(i == j)
				Dist[i][j] = 0;
			else
				Dist[i][j] = INF;
			
			Path[i][j] = j;			//注意不同的路径回溯有着不同的初始化
		}
	
	for(i = 1; i <= Num; ++i)
	{
		scanf("%d", &num);
		while(num--)
		{
			scanf("%d%d", &j, &dist);
			Dist[i][j] = dist;
		}
	}
}

void Floyd(int Num)
{
	int i, j, k;
	for(k = 1; k <= Num; ++k)
		for(i = 1; i <= Num; ++i)
			for(j = 1; j <= Num; ++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];		//此处对应不同的路径回溯算法(法二)
				}
			}
}
	
int main()
{
	int Num, i, j, k, maxdist, ans, id;
	while(1)
	{
		scanf("%d", &Num);
		if(!Num)
			break;
		Init(Num);
		Floyd(Num);
		for(i = 1; i <= Num; ++i)
		{
			maxdist  = 0;
			for(j = 1; j <= Num; ++j)
				maxdist = max(maxdist, Dist[i][j]);	
			MaxDist[i] = maxdist;
		}

		ans = INF;
		for(i = 1; i <= Num; ++i)
		{
			if(MaxDist[i] < ans)
			{
				ans = MaxDist[i];
				id = i;
			}
		}

		if(ans != INF)
			printf("%d %d\n", id, ans);
		else
			printf("disjoint\n");
		/*
		路径回溯部分（测试用）
		for(i = 1; i <= Num; ++i)
			printf("%d %d %d %d %d %d %d %d %d\n", Path[i][1], Path[i][2], Path[i][3], Path[i][4], Path[i][5], Path[i][6], Path[i][7], Path[i][8], Path[i][9]);
		
		i = 3;
		j = 9;
		k = Path[i][j];
		printf("From %d to %d : ", i, j);
		printf("%d ---> ", i);
		while(k != j)
		{
			printf("%d ---> ", k);
			k = Path[k][j];
		}
		printf("%d   ", j);
		printf("Distance: %d  \n", Dist[i][j]);
		*/
	}

	return 0;
}



   










    

    

    回溯算法可以有很多种，如上。




 






版权声明：本文为woxiaohahaa原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。