有源点最短路径--Dijkstra算法

佚名 5年前 (2019-01-01) 算法 1309人围观抢沙发百度已收录

问题描述：一个带权有向图G与源点v，求从源点v到G中其他顶点的最短路径，并限定各边权值大于0

它的思想在于，对顶点集划分为两组，第一组为已经求出的最短路径的集合(S)，期初只有一个顶点，此后每求出一个最短路径v,....u，将顶点u加入集合S中，知道全部顶点U加入到S中，第二组即为未确最短路径的顶点集合。当然，更详细的解释可以参考书本

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

图：

略(0.0~)

#include <stdio.h>
#include <malloc.h>
#include  <iostream>
using namespace std;
#define INFINITY 32767//假设权值不超过INFINITY
#define MAX_VERTEX_NUM  20
#define TRUE true
#define FALSE false
typedef char VertexType;
typedef enum{DG,DN,UDG,UDN}GraphKind;//有向图,有向网,无向图,无向网

typedef struct
{	// 图的定义
	VertexType vexs[MAX_VERTEX_NUM]; //顶点信息
	int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
	int vexnum; // 图的当前顶点数
	int arcnum; //图的边数
	GraphKind kind; // 图的种类标志
}MGraph;

int LocateVex(MGraph G,VertexType v)
{
	int i;
	for(i=0;i<G.vexnum;i++)
	{
		if(v==G.vexs[i]) return i;
	}
	return -1;
}

void CreateDG(MGraph &G)
{
	int i,j,k,w; char flag;
	VertexType v1,v2;
	G.kind = DG;
	printf("请输入有向图的顶点数、边数\n");
	scanf("%d %d",&G.vexnum,&G.arcnum);
	printf("请依次输入顶点信息\n");
	for(i=0;i<G.vexnum;i++)
	{
		cout<<"第"<<i+1<<"个顶点为：";
		cin>>G.vexs[i];
		for(j=0;j<i;j++)
		{
			if(G.vexs[j]==G.vexs[i])break;
		}
		if(j<i)
		{
			i--;
			printf("已存在这样的顶点，请重新输入！\n");
			continue;
		}
	}

	for(i=0;i<G.vexnum;i++)
	{
		for(j=0; j<G.vexnum; j++) G.arcs[i][j]=INFINITY;
	}

	for(k=0;k<G.arcnum;k++)
	{
		cout<<"请输入一条弧尾：";
		cin>>v1;
	    cout<<"请输入一条弧头：";
		cin>>v2;
		cout<<"请输入相应边的权值：";
		cin>>w;
		i=LocateVex(G,v1); j=LocateVex(G,v2);
		if(G.arcs[i][j]==INFINITY)
		{
			G.arcs[i][j]=w;
		}
		else
		{
			printf("已存在该边，是否要重新确定其权值？按下“Y”确定，按其他键继续输入其它边\n");
			scanf("%c",&flag);
			if(flag=='y'||flag=='Y')
			{
				G.arcs[i][j]=w;
			}
			k--;
		}
	}//end of for
}

void Dijkstra(MGraph G,int v0,bool P[][MAX_VERTEX_NUM], int D[])
{
	int final[MAX_VERTEX_NUM];
	int v,i,j,w; int min;
	for(v=0;v<G.vexnum;++v)
	{
		final[v]=FALSE; D[v]=G.arcs[v0][v];
		for(w=0;w<G.vexnum;++w) P[v][w]=FALSE;
		if(D[v]<INFINITY) {P[v][v0]=TRUE;P[v][v]=TRUE;}
	}
	D[v0]=0; final[v0]=TRUE;
	for(i=1;i<G.vexnum;++i)//其余G.vexnum-1个顶点
	{
		min=INFINITY;
		for(w=0; w<G.vexnum; ++w)
		{
			if(!final[w] && D[w]<min)
			{
				v=w; min=D[w];
			}
		}
		final[v]=TRUE;
		for(w=0;w<G.vexnum;++w)
		{
			if(!final[w] && min+G.arcs[v][w]<D[w])
			{
				D[w]=min+G.arcs[v][w];
				for(j=0;j<G.vexnum ;++j) P[w][j]=P[v][j];
				P[w][w]=TRUE;
			}
		}
    }
}

int  main()
{
	MGraph G; char v;int v0,i,j;
	int D[MAX_VERTEX_NUM];
	bool P[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
	CreateDG(G); printf("请输入源点编号：");
	cin>>v; v0=LocateVex(G,v); Dijkstra(G,v0,P,D);
	for(i=0;i<G.vexnum;i++)
	{
		printf("编号为%c的顶点到编号为%c的顶点的最短路径长度为：%d，路经为：",v,G.vexs[i],D[i]);
		for(j=0;j<G.vexnum&&P[i][j];j++) printf("%c ",G.vexs[j]);
		printf("\n");
	}
}

　　运行结果：