一.最短路

1.定义

一个图中的一个点到另一个点的最短路径（废话

2.性质

1. 对于边权为正的图，任意两个结点之间的最短路，不会经过重复的结点。

2. 对于边权为正的图，任意两个结点之间的最短路，不会经过重复的边。

3. 对于边权为正的图，任意两个结点之间的最短路，任意一条的结点数不会超过 n ，边数不会超过 n - 1。

二.Dijkstra

Dijkstra（/ˈdikstrɑ/或/ˈdɛikstrɑ/）算法由荷兰计算机科学家 E. W. Dijkstra 于 1956 年发现，1959 年公开发表。是一种求解 非负权图 上单源最短路径的算法。

1.原理

贪心求离源点最近的点

2.实现

核心代码很简单

十行左右

for (long long i = 1; i < n; i++) 
        {
            minn = INT_MAX;
            for (long long j = 1; j <= n; j++) 
                if (v[j] == 0 && minn > dis[j]) 
                {
                    minn = dis[j];
                    pos = j;
                }
            v[pos] = 1;
            for (long long j = 1; j <= n; j++) 
                if (!v[j] && dis[j] > dis[pos] + ma[pos][j]) 
                    dis[j] = dis[pos] + ma[pos][j];
        }

n表示有n个点

ma[i][j]表示从i号点到j号点的路径其中

v[i]表示i号节点有没有被选用， 1为选用，反之则没有

dis[i]表示源点（1号点）到i号点的当前最短路径

三.例题

在 vjudge 上找的题

UESTC-30 传送门->UESTC-30

题目大意：

从1到 N 的最短路

思路

对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间。

妥妥的模板题

不多说，上代码

code

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
long long dis[N], ma[N][N], v[N];
long long n, m;

int main() 
{
    while (1) 
    {
        cin >> n >> m;
        if (!n && !m) 
            break;      //0, 0跳出
        for (long long i = 1; i <= n; i++) 
            for (long long j = 1; j <= n; j++) 
                ma[i][j] = INT_MAX;       //注意初始化
        for (long long i = 1; i <= m; i++) 
        {
            long long a, b, c;
            cin >> a >> b >> c;
            ma[a][b] = ma[b][a] = min(c, ma[a][b]);//可能有重边
        }
        long long i, j, pos = 1, minn, sum = 0;
        memset(v, 0, sizeof(v));          //注意初始化
        for (long long i = 1; i <= n; i++) 
        {
            dis[i] = ma[1][i];
        }
        v[1] = 1;
        dis[1] = 0;
        for (long long i = 1; i < n; i++) //Dijkstra
        {
            minn = INT_MAX;
            for (long long j = 1; j <= n; j++)
                if (v[j] == 0 && minn > dis[j]) 
                {
                    minn = dis[j];
                    pos = j;
                }
            v[pos] = 1;
            for (long long j = 1; j <= n; j++) 
                if (!v[j] && dis[j] > dis[pos] + ma[pos][j]) 
                    dis[j] = dis[pos] + ma[pos][j];
        }
        cout << dis[n] << endl;
    }

    return 0;
}