背景知識

1. 圖簡介：圖由節(jié)點和邊組成，邊有方向的圖稱為有向圖，邊沒有方向的圖稱為無向圖，最短路徑算法里可以把無向圖視為雙向連接的有向圖。 邊有權重的圖稱為有權圖，邊沒有權重的圖稱為無權圖，無權圖可以視為邊的權重均為1的圖。
2. 單源點最短路徑：給定圖中的一個節(jié)點，求該節(jié)點到其他所有節(jié)點的最短路徑。

Dijkstra算法

Dijikstra算法就是為了解決單元最短路徑問題?？梢越鉀Q有向正權圖和無向圖，為什么不可以是負權圖呢？我們后面再做討論。
一.核心思想
我們設G=(V,E)為一個帶權有向圖，我們可以把圖中的節(jié)點分為兩組:

• 一組為已經(jīng)求出最短路徑的頂點集合S，如果后續(xù)求出來一條最短路徑那就把端點加入到集合S中，
• 二組為未確定最短路徑的節(jié)點集合U。
  同時，我們定義一個dist[i] 用來表示 從i節(jié)點到源點的最小距離。

二.步驟

1. 初始化，源點加入到S中， 其他節(jié)點加入到U中。將起始節(jié)點start的所有可達節(jié)點的最短路徑長度置為edge(start, arriveNode),
2. 遍歷curr可以達到的集合U中的節(jié)點(u)，更新過程中:
   如果dist[curr] + edge(curr,u) < dist[u],那么更新dist[u] = dist[curr] + edge(curr,u)
   最后找到U集合中距離源點路徑最短的節(jié)點，即我們上面所求的dist[u]值最小節(jié)點u，加其入到S集合中，然后將 u 節(jié)點作為下次遍歷的 curr 節(jié)點（也就是這個u節(jié)點是我們S集合中距離源點最長的節(jié)點了）
3. 重復步驟2
   參考過程：
   
   image.png
   
   三.負權圖無法判定的原因
   
   image.png
   
   上圖中，顯然0-1-1是我們的最短路徑，在此算法中第一步，我們按照步驟尋找U集合里面的最小路徑，將節(jié)點0，2分別添加到S集合中，于是我們的curr節(jié)點變?yōu)?，然后我們把1節(jié)點加入，所以算法結束答案計算0-2的最短路徑應該是2而不是1。綜上，Dijkstra算法不適合于邊權值為負值的圖。
   四.有向圖和無向圖代碼
   我們根據(jù)一個題目來理解用法：
   
   image.png

#include <iostream>
#include <climits>
using namespace std;
int n, m, start, endIndex;
int ways[2501][2501];           
long long dist[2501];
bool visited[2501] = {false};
int main(){
    cin >> n >> m >> start >> endIndex;
    //路徑默認為極大值
    for (int i = 0; i <= 2500; i++)//init
        for (int j = 0; j <= 2500; j++)
            ways[i][j] = INT_MAX;
    fill(dist, dist + 2501, INT_MAX);
    //填充路徑
    for(int i = 0; i < m; i++){
        int from , to, value;
        scanf("%d %d %d",&from, &to, &value);
        if(value < ways[from][to]){
            ways[from][to] = ways[to][from] = value; 
        }
    }
    //初始化
    dist[start] = 0;
    int min_value_index, min_value; //定義每次從集合U中最小路徑下標以及最小路徑
    while(true){
        min_value_index = -1;
        min_value = INT_MAX;
        //找到集合U中的最小路徑下標和最小路徑
        for(int i = 1; i <= n; i++){
            if(!visited[i] && min_value > dist[i]){
                min_value_index = i;
                min_value = dist[i];
            }
        }
        //如果所有節(jié)點都已經(jīng)遍歷過找到最小路徑長度，那么直接跳出。
        if(min_value_index == -1) break;
        //將min_value_index元素加入到visited中
        visited[min_value_index] = true;
        //遍歷更新U集合中每一個節(jié)點的距離
        for(int i = 1; i <= n; i++){
            if(!visited[i]){
                dist[i] = min(dist[i], dist[min_value_index] + ways[min_value_index][i]);
            }
        }
    }
    // print answer
    cout << dist[endIndex];
    return 0;
}