【算法】最短路径之Dijkstra（I）

1.算法描述

lowcost[i]记录源点到点i的最短距离，visit[i]表示点i已被访问过，Un表示未访问节点的集合， Vi表示已访问节点的集合。

(1)寻找具有最小lowcost值的节点j

(2)将(1)中节点j标记已访问，visit[ j ]=1，并更新lowcost数组

(3)直至访问完所有节点，即Un为空。

在源代码中，min_node表示节点j，min_lowcost表示最小lowcost。

2. 问题

2.1 POJ 2387

注意：有重边（即一条边可能有多次输入），边的长度不是题目中1~100。

memset(,inf,)函数不能这样用。

源代码：

2387

Accepted

4084K

79MS

C

1269B

2013-07-15 10:35:52

#include "stdio.h"
#include "stdlib.h"

#define MAX 1000
#define inf 0xffffff

int dis[MAX][MAX];

void init(int T,int N)
{
	int i,j,from,to,len;
	for(i=0;i<N;i++)
	{
		for(j=0;j<i;j++)
			dis[i][j]=dis[j][i]=inf;
		dis[i][i]=0;
	}
	
	for(i=1;i<=T;i++)
	{
		scanf("%d%d%d",&from,&to,&len);
		if(len<dis[from-1][to-1])
			dis[from-1][to-1]=dis[to-1][from-1]=len;
	}	
}

int smaller(int be,int af)
{
	return be<=af?be:af;
}

void dijkstra(int N)
{
	int i,count=1,min_lowcost,min_node;
	int *lowcost=(int *) malloc(N*sizeof(int));
	int *visit=(int *) malloc(N*sizeof(int));
	
    for(i=0;i<N;i++)
	{
		lowcost[i]=inf;
		visit[i]=0;
	}
	
	lowcost[N-1]=0;
	visit[N-1]=1;
	min_node=N-1;
	
	while(count<=N)
	{
        min_lowcost=inf; 
		
		for(i=0;i<N-1;i++)
		{
			if(!visit[i]&&dis[min_node][i]!=inf)
				lowcost[i]=smaller(lowcost[i],lowcost[min_node]+dis[min_node][i]);
		}
		
		for(i=0;i<N-1;i++)
			if(!visit[i]&&lowcost[i]<min_lowcost)
			{
				min_lowcost=lowcost[i];
				min_node=i;
			}
			
			visit[min_node]=1;     	
			count++;
	}
	printf("%d\n",lowcost[0]);
	free(lowcost);
	free(visit);
}

int main()
{
	int T,N;
	scanf("%d%d",&T,&N);				
	init(T,N);	
	dijkstra(N);
	
	return 0;
}

2.2 POJ 2253

源点是Freddy's stone，汇点是Fiona's stone。源点到汇点的每一通路均有一条最长边，在这些最长边中找出最小值，最小值即为Frog Distance。

Dijkstra算法求解（源点到图中其他点）所有通路中的最短路径，其松弛条件：

为求解最小最长边，将松弛条件修改为

其中，dis[i]记录源点到点i所有通路的最长边。

源代码：

2253

Accepted

504K

16MS

C

1673B

2013-07-16 09:40:43

#include "stdio.h"
#include "stdlib.h"
#include "math.h"

#define MAX 200
#define inf 0xffff

double edge[MAX][MAX];

typedef struct
{
	int x,y;
}Tpoint;

Tpoint point[MAX];

double distance(Tpoint p1,Tpoint p2)
{
	return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}

void init(int n)
{
	int i,j;
	for(i=0;i<n;i++)
		scanf("%d%d",&point[i].x,&point[i].y);
	
	for(i=0;i<n;i++)
	{
		for(j=0;j<i;j++)
			edge[i][j]=edge[j][i]=distance(point[i],point[j]);
		edge[i][i]=0;          
	}	
}

double smaller(double be,double af)
{
	return be<=af?be:af;
}

double larger(double be,double af)
{
	return be>=af?be:af;
}

void dijkstra(int n)
{
	int i,count=1,min_node;
	double min_dis;
	double *dis=(double *) malloc(n*sizeof(double));
	int *visit=(int *) malloc(n*sizeof(int));
	
    for(i=0;i<n;i++)
	{
		dis[i]=inf;
		visit[i]=0;
	}
	
	dis[0]=0;
	visit[0]=1;
	min_node=0;
	
	while(count<=n)
	{
        min_dis=inf; 
		
		for(i=1;i<n;i++)
		{
			if(!visit[i])
				dis[i]=smaller(larger(dis[min_node],edge[min_node][i]),dis[i]);
		}
		
		for(i=1;i<n;i++)
			if(!visit[i]&&dis[i]<min_dis)
			{
				min_dis=dis[i];
				min_node=i;
			}
			
			visit[min_node]=1;     	
			count++;
	}
	printf("%.3f\n\n",dis[1]);
	free(dis);
	free(visit);
}

int main()
{
	int n,coun=1;
	while(scanf("%d",&n)&&n!=0)
	{
		init(n);
		printf("Scenario #%d\n",coun);
		printf("Frog Distance = ");
		dijkstra(n);
		coun++;
	}	
	return 0;
}

2.3 POJ 1502

求解最短路径中最长边，输入采用的是Discuss中conan521的小技巧。

源代码：

1502

Accepted

408K

0MS

GCC

1491B

2013-08-08 20:16:00

#include "stdio.h"
#include "stdlib.h"

#define MAX 100
#define inf 0xffff

int edge[MAX][MAX];

void init(int N)
{
    int i,j,m;
    for(i=1;i<N;i++)
    {
        for(j=0;j<i;j++)
        {
            if(scanf("%d",&m)!=0)
                edge[i][j]=edge[j][i]=m;
            else
            {
                edge[i][j]=edge[j][i]=inf;
                scanf("x");
            }
        }
        edge[i][i]=0;
    }
}

int smaller(int be,int af)
{
    return be<=af?be:af;
}

void dijkstra(int N)
{
    int i,count=1,min_lowcost,min_node;
    int *lowcost=(int *) malloc(N*sizeof(int));
    int *visit=(int *) malloc(N*sizeof(int));

    for(i=0;i<N;i++)
    {
        lowcost[i]=inf;
        visit[i]=0;
    }

    lowcost[N-1]=0;
    visit[N-1]=1;
    min_node=N-1;

    while(count<N)
    {
        min_lowcost=inf; 

        for(i=0;i<N-1;i++)
        {
            if(!visit[i]&&edge[min_node][i]!=inf)
                lowcost[i]=smaller(lowcost[i],lowcost[min_node]+edge[min_node][i]);
        }

        for(i=0;i<N-1;i++)
            if(!visit[i]&&lowcost[i]<min_lowcost)
            {
                min_lowcost=lowcost[i];
                min_node=i;
            }
        visit[min_node]=1;
        count++;
    }
    printf("%d\n",min_lowcost);
    free(lowcost);
    free(visit);
}

int main()
{
    int N;
    scanf("%d",&N);                
    init(N);  
    dijkstra(N);

    return 0;
}