iT邦幫忙

1

資結經典題目: 實作Dijkstra's algorithm,求graph中其中一個點到其它點的最短距離

嗨嗨,大家好,
今天分享自己實作Dijkstra's algorithm演算法的過程,
Dijkstra's algorithm是用來求一個graph從一個頂點出發,
走到其它點的最短距離,
例如說我有一個graph如下圖:
https://ithelp.ithome.com.tw/upload/images/20200614/201171148cqWv6tJyK.png

每條邊都是有方向性和權重的,
那麼如果頂點0當作起點,

  • 0到0的最短距離為0(在原地不動)
  • 0到1的最短距離為100
  • 0到2的最短距離為200

關於Dijkstra's algorithm的細節,
代克思托演算法 (Dijkstra's algorithm)中有例子可以看,
有細講每個步驟是怎麼做的

我的實作程式碼:

#include <iostream>
#include <vector>
#include <deque>
#include <queue>
#include <list>
using namespace std;

//實作graph,頂點編號為0~n-1
class Graph
{

//general的狀況,定義在graph中的節點結構
    class GraphNode
    {
    public:
        GraphNode() {};
        GraphNode(int n) :node(n) {};
        GraphNode(int n, int w) :node(n), weight(w) {};
        int node; //頂點編號
        int weight; //for weighted graph
    };

public:
    int n; //頂點數量
    vector<list<GraphNode>> L; // adjacency list,記錄每個頂點相鄰的頂點

    Graph (int n)
    {
        this->n = n;
        this->L = vector(n, list<GraphNode>());
    }

    void set_edge (int v_i, int v_j, int weight)
    {

        // 若是無向圖的(v_i, v_j) 和 (v_j, v_i)相同
        // 若是有向圖只能設一邊
        L[v_i].push_back(GraphNode(v_j, weight));
        //L[v_j].push_back(GraphNode(v_i, weight));

    }

    /*
       函數功能: 從src出發,
       用Dijkstra's algorithm算法,
       求src點到其它點的最短距離
    */
    vector<long long> Dijk_BFS(int src)
    {

        long long inf = (long long)1<<32;
        vector<long long> dp(n, inf);//一開始,走到每個點的距離都是無限大
        dp[src] = 0; //起點到起點的最短距離就是0,因為不用動

        int pt = src;

        for(int i=0; i<n; i++)
        {
            auto cmp = [](GraphNode & a, GraphNode & b)
            {
                return a.weight > b.weight;
            };
            priority_queue <GraphNode, vector<GraphNode>, decltype(cmp)>  min_heap(cmp);

            for (auto it = L[pt].begin(); it != L[pt].end(); it++)
            {
                min_heap.push(*it);
            }
            // 已經無路可走了
            if(min_heap.empty())
            {
                break;
            }
            int next = min_heap.top().node;
            while (!min_heap.empty())
            {
                GraphNode node = min_heap.top();
                min_heap.pop();
                dp[node.node]= min(dp[node.node], dp[pt]+node.weight);
            }
            pt = next;
        }
        return dp;
    }
};

int main()
{
    Graph G(3); //創建有3個node的graph
    G.set_edge(0, 1, 100);
    G.set_edge(1, 2, 100);
    G.set_edge(0, 2, 500);
    vector<long long> distance =  G.Dijk_BFS(0);
    for(auto d: distance)
    {
        cout<<d<<' ';
    }
    cout << endl;
    return 0;
}

類似練習題

參考題目: leetcode- 787. Cheapest Flights Within K Stops

乍看之下,這個問題跟Dijkstra's algorithm很像,
都是從某個起點出發,
要找到某個點的最短距離,
但此題多了最多只能走K+1步的限制,
要想辦法對原算法做變形。

一開始也把到每個點的距離都設成無限大,
但每次迭代時,
所有舊的點(走i步可以到的地方)都要拿來更新走i+1步可以到的最短距離

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        long long inf = (long long)1<<32;
        vector<long long> dp(n, inf);//一開始,飛到每個點的距離都是無限大
        dp[src] = 0; //起點到起點的最短距離就是0,因為不用動
        //題意說最多停留K站,其實就是可以飛K+1次
        for (int i = 0; i <= K; ++i) {
            vector<long long> t = dp;
            for (auto x : flights) {
                if(dp[x[0]]<inf && dp[x[0]] + x[2]< t[x[1]]){
                    t[x[1]] = dp[x[0]] + x[2];
                }
            }
            dp = t;
        }
        return dp[dst] >= inf ? -1 : dp[dst];
    }
};

參考資料

  1. 代克思托演算法 (Dijkstra's algorithm)

尚未有邦友留言

立即登入留言