Dijkstra 最短路径

// Dijkstra.cpp : Defines the entry point for the console application.

// 最短路径

#include "stdafx.h"

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define N 120

#define MaxInt 0x3f3f3f3f

int n,m;

int map[N][N], visited[N],low[N];

void Dijkstra()

{

int pos = 1, i , j ,min;

memset(visited, 0, sizeof(visited));

for(i = 1; i<=n ;i++)

low[i] = map[pos][i];

visited[1] = 1;

for(i = 1;i < n; i++)

{

min = MaxInt;

for(j = 1;j<=n;j++)

 if(visited[j] == 0 && min > low[j])

 {

 min = low[j];pos = j;

 }

 visited[pos] = 1;

 for(j = 1;j <= n;j++)

 if(visited[j] == 0 && low[j] > low[pos]+map[pos][j])

 low[j] = low[pos]+map[pos][j];

}

for( int k = 1; k<=n ;k++)

printf("%d\n",low[k]);

}

int _tmain(int argc, _TCHAR* argv[])

{

int i,j;

char v[50];

while(scanf("%d", &n)!=EOF)

{

memset(map,MaxInt,sizeof(map));

for(i = 1; i <= n; i++)

map[i][i] = 0;

//m = n*(n-1)/2;

for(i = 2; i <=n;i++)

for(j = 1;j < i;j++)

{

scanf("%s", &v);

if(strcmp(v, "x")!=0)

map[i][j] = map[j][i]=atoi(v);

}

printf("before Dijkstra:\n");

Dijkstra();

printf("after Dijkstra:\n\n");

}

return 0;

}