dijkstra算法（有权图，无权图）：
带权路径长度——当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度

初始化三个数组，final标记各顶点是否已找到最短路径，dist最短路径长度，path路径上的前驱

 不断循环更新最短路径长度

 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int INF = 1000000;
int main() {int n, g[205][205];cin >> n;for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) {if (i == j)g[i][j] = 0;else g[i][j] = INF;}for (int i = 1; i <= n - 1; i++) {for (int j = i + 1; j <= n; j++) {cin >> g[i][j];}}int dis[205], book[205];memset(book, 0, sizeof(book));          for (int i = 1; i <= n; i++)dis[i] = g[1][i];dis[1] = 0;book[1] = 1;for (int i = 2; i <= n; i++) {int minn= INF, u;for (int j = 1; j <= n; j++) {if (!book[j] && dis[j] < minn) {minn= dis[j];u = j;}}book[u] = 1;for (int j = 1; j <= n; j++) {dis[j] = min(dis[j], dis[u] + g[u][j]);}}cout << dis[n];return 0;
}

第一个循环创数组，默认所有点之间的距离为无穷大(用一个大整型来表示)，第二个循环输入数据，记录每个点之间的实际距离，dis是从一个点到其他点的距离数组，book是用来记录这个点是否被到达过的数组，后面的循环就是每次从一个点出发，找到与其距离最短的点并记录，同时更新到达其他点的距离