すべてはシュタインズゲートの選択だ最短路径问题求解 2015-08-31

华为机试－3

题目

需求

Jack周日去动物园看“猩猩”，为了直达目的地，Jack想根据动物园地图计算从园区入口到“猩猩”馆的最短路径是多长？

输入

5 4
0 7 3 10 15
7 0 5 13 12
3 5 0 5 10
10 13 5 0 11
15 12 10 11 0

输入说明

输入中第一行第一个数为动物园展览馆总数n(包括0号馆)，第二个数为“猩猩”馆的数字编号(入口编号为0号馆)。后面的输入是一个n×n的矩阵，表示动物园地图，其中，矩阵节点之间用一个空格隔开，矩阵节点的值n[i][j]代表i号馆到j号馆的距离,0表示馆间不通或无效路径。

输出

13 //最短路径长度

求解

采用Dijstra算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <stdio.h>
#include <iostream>

#define V_MAX 26
#define MAXVALUE 32767

using namespace std;
typedef struct
{
	char Vertex[V_MAX];
	int Edges[V_MAX][V_MAX];
	int isTrav[V_MAX];
	int VNum;
	int EgdeNum;
}MatrixGraph;

int CreateMatrixGriph(MatrixGraph *G)
{
	int obj;
	scanf("%d %d",&G->VNum,&obj);

	for(int i=0; i<G->VNum; i++) {
		G->Vertex[i] = '0'+i;
	}

	for(int i=0; i<G->VNum;i++)
	{
		for(int j=0; j<G->VNum; j++)
		{
			cin>>G->Edges[i][j];
		}
	}

	G->EgdeNum = G->VNum * G->VNum;
	return obj;
}

int Dijkstra(MatrixGraph G, int obj)
{
	int weight[V_MAX];
	int path[V_MAX];
	int tmpvertex[V_MAX];
	int i,j,k,v0,min;
	v0 = 0;
	for(i=0;i<G.VNum;i++)
	{
		weight[i] = G.Edges[v0][i];
		if(weight[i]<MAXVALUE && weight[i]>0)
			path[i] = v0;
		tmpvertex[i] = 0;
	}
	tmpvertex[v0] = 1;
	weight[v0] = 0;
	for(i=0;i<G.VNum;i++)
	{
		min = MAXVALUE;
		k = v0;
		for(j=0; j<G.VNum; j++)
			if(tmpvertex[j]==0 && weight[j]<min)
			{
				min = weight[j];
				k = j;
			}
		tmpvertex[k] = 1;
		for(j=0; j<G.VNum; j++)
			if(tmpvertex[j]==0 && weight[k]+G.Edges[k][j]<weight[j])
			{
				weight[j] = weight[k] + G.Edges[k][j];
				path[j] = k;
			}
	}

	return weight[obj];
}

int main()
{
	MatrixGraph G;
	int obj = CreateMatrixGriph(&G);
	printf("%d\n", Dijkstra(G,obj));
	return 0;
}

结果

输出结果

▲