数据结构-迪杰斯特拉最短路径算法 （C++代码）

解题思路:

        讲不出来，卖个萌。 实质也是贪心。

参考代码:

#include<bits/stdc++.h>
#define Inf 0xFFFFFF
using namespace std;
const int mapSize = 51;

int  Map[mapSize][mapSize];
int  dis[mapSize];
bool Vis[mapSize];
int  point, start;

void Dijkstra() {
	Vis[start] = true;
	for (int i = 0; i < point; i++) {
		dis[i] = Map[start][i] != 0 ? Map[start][i] : Inf;
	} dis[start] = 0;

	for (int poi = 1; poi < point; poi++) {
		int min = Inf, index;

		for (int i = 0; i < point; i++)
			if (!Vis[i] && dis[i] < min) {
				min = dis[i]; index = i;
			}
			
		Vis[index] = true;
		
		for (int i = 0; i < point; i++)
			if (!Vis[i] && Map[index][i] != 0 && dis[i] > dis[index] + Map[index][i])
				dis[i] = dis[index] + Map[index][i];
	}
}

int main() {
	cin >> point >> start;
	for (int i1 = 0; i1 < point; i1++)
		for (int i2 = 0; i2 < point; i2++)
			cin >> Map[i1][i2];

	Dijkstra();
	for (int i = 0; i < point; i++) {
		if(i != start)
			dis[i] < Inf ? cout << dis[i] << ' ' : cout << -1 << ' ';
	}
	cout << endl;
}