1366 - 算法7-15：迪杰斯特拉最短路径算法

4 1
0 3 0 1
0 0 4 0
2 0 0 0
0 0 1 0

6 4 7 

Hint

在本题中，需要按照题目描述中的算法完成迪杰斯特拉算法，并在计算最短路径的过程中将每个顶点是否可达记录下来，直到求出每个可达顶点的最短路径之后，算法才能够结束。
迪杰斯特拉算法的特点是按照路径长度递增的顺序，依次添加下一条长度最短的边，从而不断构造出相应顶点的最短路径。
另外需要注意的是，在本题中为了更方便的表示顶点间的不可达状态，可以使用一个十分大的值作为标记。

Solution C

#include <stdio.h>
#include <string.h>
int edge[51][51],isvisited[51],n,m,s,lowcost[51];
void dijkstra(int vo){
	int i,j,min,pre;
	isvisited[vo]=1;
	for (i=0;i<n;i++)
	{
		lowcost[i]=edge[vo][i];

	}
	lowcost[vo]=0;
	pre=vo;
	for (i=1;i<n;i++)
	{
		min=100000000;
		for (j=0;j<n;j++)
		{
			if (isvisited[j]==0&&min>lowcost[j])
			{
				min=lowcost[j];
				pre=j;
			}
		}
		isvisited[pre]=1;
		for (j=0;j<n;j++)
		{
			if (isvisited[j]==0&&lowcost[j]>edge[pre][j]+lowcost[pre])
			{
				lowcost[j]=edge[pre][j]+lowcost[pre];
			}
		}
	}
}
int main(){
	int i,j;
//	freopen("1.txt","r",stdin);
	while (scanf("%d %d",&n,&s)!=EOF)
	{
		memset(isvisited,0,sizeof(isvisited));
		for (i=0;i<n;i++)
		{
			for (j=0;j<n;j++)
			{
				scanf("%d",&edge[i][j]);
				if (edge[i][j]==0)
				{
					edge[i][j]=100000000;
				}
			}
		}
		dijkstra(s);
		for (i=0;i<n;i++)
		{
			if (i!=s)
			{
				if (lowcost[i]==100000000)
				{
					printf("-1 ");
				}else{
					printf("%d ",lowcost[i]);
				}
			}
		}
		printf("\n");
	}
//	fclose(stdin);
	return 0;
}

Solution C++

#include <cstdio>
#include <cstdlib>
#include <stack>
#include <algorithm>
using namespace std;
const int MAXN = 50;
const int INF = 1000000000;
int mat[MAXN][MAXN], min_distance[MAXN], v[MAXN];
int n, s;

void dijkstra() {
	int i, j, k;
	for (i = 0; i < n; i++) {
		min_distance[i] = INF;
		v[i] = 0;
	}
	for (min_distance[s] = 0, j = 0; j < n; j++) {
		for (k = -1, i = 0; i < n; i++) {
			if (!v[i] && (k == -1 || min_distance[i] < min_distance[k])) {
				k = i;
			} 
		}
		for (v[k] = 1, i = 0; i < n; i++) {
			if (!v[i] && min_distance[k] + mat[k][i] < min_distance[i]) {
				min_distance[i] = min_distance[k] + mat[k][i];
			} 
		}
	}
}
int main() {
	scanf("%d%d", &n, &s);
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			scanf("%d", &mat[i][j]);
			if (mat[i][j] == 0)
				mat[i][j] = INF;
		}
	}
	dijkstra();
	for (int i = 0;i < n;i++) {
		if (i != s) {
			if (min_distance[i] < INF)
				printf("%d ", min_distance[i]);
			else
				printf("%d ", -1);
		}
	}
	puts("");
	return 0;
}