dijkstra算法计算从S到T的最短路径

[c++]代码库

#include<iostream>
#include<string>
#include<cstdio>

using namespace std;
#define INF 0x7f7f7f7f

const int N = 1005; //点的个数上限

int maze[N][N];
int dis[N];
bool vis[N];

//点的个数和边的条数
int n, m, S, T, K;

void init()
{
	memset(maze, INF, sizeof(maze));
	memset(dis, INF, sizeof(dis));
	memset(vis, false, sizeof(vis));
}

void dijkstra(int st)
{
	dis[st] = 0;
	for (int i = 1; i <= n; i++)
	{
		//找到和起点距离最短的点
		int minx = INF;
		int minmark;
		for (int j = 1; j <= n; j++)
		{
			if (vis[j] == false && dis[j] <= minx)
			{
				minx = dis[j];
				minmark = j;
			}
		}
		//并标记
		vis[minmark] = true;
		cout << minmark << endl;
		//更新所有和它连接的点的距离
		for (int j = 1; j <= n; j++)
		{
			if (vis[j] == false && dis[j] > dis[minmark] + maze[minmark][j])
				dis[j] = dis[minmark] + maze[minmark][j];                                                                                                   
		}
	}
}


int main()
{                                                                                                                                                                                                                                         
	cin >> n >> m >> S >> T >> K;
		init();
		for (int i = 1; i <= m; i++)
		{
			int x, y, len;
			scanf("%d %d %d", &x, &y, &len);
			if (x != y && maze[x][y] > len)
			{
				maze[y][x] = len;
				maze[x][y] = len;
			}
		}
		//以S为起点跑一次dij
		dijkstra(S);
		//输出到T的距离
		printf("%d\n", dis[T]);
		return 0;
	}