博客

最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：

1.确定起点的最短路径问题：即已知起始结点，求最短路径的问题。适合使用Dijkstra算法。

2.确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。

3.确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。

4.全局最短路径问题：求图中所有的最短路径。适合使用Floyd算法。

这里只给出第1种和第四种情况下两种算法的源代码。

#include "stdio.h"
#define MAX 99

typedef struct                    //图的邻接矩阵存储结构体定义
{
	int vexs[6];
	int arcs[6][6];
	int n, e;
}MGraph;

void create(MGraph &G);                 //图的创建
void Dijkstra(MGraph G, int u);         //Dijkstra算法
void Floyd(MGraph G);                   //Floyd算法

int main()
{
	MGraph G;
	create(G);
	printf("最短路径之Dijkstra算法：\n");
	Dijkstra(G, 0);
	printf("最短路径之Floyd算法：\n");
	Floyd(G);

	return 0;
}

void create(MGraph &G)
{
	int i, j;
	printf("请输入顶点数和边数：\n");
	scanf("%d %d", &G.n, &G.e);

	int b[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
	for(i = 0; i < G.n; ++i)
		G.vexs[i] = b[i];
	printf("顶点编号分别为：\n");
	for(i = 0; i < G.n; ++i)
		printf("%d ", G.vexs[i]);

	int a[6][6]={
		{0, 3, MAX, MAX, MAX, MAX},
		{MAX, 0, 2, MAX, 6, 7},
		{MAX, MAX, 0, 1, 3, 4},	
		{MAX, MAX, MAX, 0, 1, MAX},
		{MAX, MAX, MAX, MAX, 0, 1},	
		{MAX, MAX, MAX, MAX, MAX, 0}
	};
	for(i = 0; i < 6; ++i)
		for(j = 0; j < 6; ++j)
		      G.arcs[i][j]=a[i][j];
	printf("\n该图的邻接矩阵：\n");
	for(i = 0; i < G.n; ++i)
	{
		for(j = 0; j < G.n; ++j)
			printf("%d ", G.arcs[i][j]);
		printf("\n");
	}
}
//Dijkstra算法
void Dijkstra(MGraph G, int u)        //假设此处从顶点0开始
{
	int i, j, k, min;
	int pre[10], final[10], dist[10];
	for(j = 0; j < G.n; ++j)
	{
		dist[j] = G.arcs[u][j];
		if(G.arcs[u][j] == MAX)
			pre[j] = -1;
		else
			pre[j] = u;
		final[j] = 0;
	}
	for(i = 1; i < G.n; ++i)
	{
		min = MAX;
		for(j = 1; j < G.n; ++j)   	//找出最小值的结点
			if( (!final[j]) && (min > dist[j]))
			{
				min = dist[j];
				k = j;
			}
		if(min == MAX)    //找不到
			break;
		final[k] = 1;   //加入该结点
		for(j = 1; j < G.n; ++j)  //更新最短路径
		{
			if((!final[j]) && (dist[j] > (dist[k] + G.arcs[k][j])))
			{
				dist[j] = dist[k] + G.arcs[k][j];
				pre[j] = k;
			}
		}
	}
	for(i = 1; i < G.n; ++i)       //输出路径与距离
	{
		if(pre[i] == -1)
		{
			printf("顶点%d到源点%d不可达。\n", i, u);
			continue;
		}
		printf("(%d, %d) = %d\n", i, u, dist[i]);
     	printf("路径为:");
	    j = i;
		while(j)
		{
			printf("%d→", j);
			j = pre[j];
		}
		printf("0\n");
	}
}
//Floyd算法
void Floyd(MGraph G)
{
	int i, j, k, dist[10][10], pre[10];
	for(i = 0; i < G.n; ++i)
		for(j = 0; j < G.n; ++j)
		{
			dist[i][j] = G.arcs[i][j];
			if(dist[i][j] != MAX)
				pre[j] = i;
			else
				pre[j] = -1;
		}
			
	for(k = 0; k < G.n; ++k)
		for(i = 0; i < G.n; ++i)
			for(j = 0; j < G.n; ++j)
				if((i != j) && (dist[i][j] > dist[i][k] + dist[k][j]))
				{
					dist[i][j] = dist[i][k] + dist[k][j];
					if(dist[i][j] != MAX)
					{
						pre[j] = k;
						pre[k] = i;
					}
					else
						pre[j] = -1;
				}
	for(i = 0; i < G.n; ++i)
		for(j = 0; j < G.n; ++j)
		{
			if(dist[i][j] == MAX)
				continue;
			else if(i != j)
				printf("(%d, %d) = %d\n", i, j, dist[i][j]);
		}
	printf("其余顶点之间不可达!\n");
}

示例：（读者可自行验证）