• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Reiks的技術(shù)博客

            C/C++/STL/Algorithm/D3D
            posts - 17, comments - 2, trackbacks - 0, articles - 0
              C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理

            Dijkstra

            Posted on 2009-08-28 09:14 reiks 閱讀(281) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 算法與數(shù)據(jù)結(jié)構(gòu)

             

            #include <iostream>
            #include 
            <vector>
            #include 
            <list>
            #include 
            <iterator>
            #include 
            <algorithm>
            #include 
            <numeric>
            #include 
            <functional>
            #include 
            <climits>
            using namespace std;

            int n;                    // n : 頂點(diǎn)個(gè)數(shù) 
            vector<vector<int> > g; // g : 圖(graph)(用鄰接矩陣(adjacent matrix)表示) 
            int s;                    // s : 源點(diǎn)(source) 
            vector<bool> known;        // known : 各點(diǎn)是否知道最短路徑 
            vector<int> dist;        // dist : 源點(diǎn)s到各點(diǎn)的最短路徑長(zhǎng) 
            vector<int> prev;        // prev : 各點(diǎn)最短路徑的前一頂點(diǎn)

            void Dijkstra()            // 貪心算法(Greedy Algorithm) 
            {
                known.assign(n, 
            false);
                dist.assign(n, INT_MAX);
                prev.resize(n);            
            // 初始化known、dist、prev。 
                dist[s] = 0;            // 初始化源點(diǎn)s到自身的路徑長(zhǎng)為0。 
                for (;;)
                
            {
                    
            int min = INT_MAX, v = s;
                    
            for (int i = 0; i < n; ++i)
                        
            if (!known[i] && min > dist[i])
                            min 
            = dist[i], v = i;    // 尋找未知的最短路徑長(zhǎng)的頂點(diǎn)v, 
                    if (min == INT_MAX) break;        // 如果找不到,退出; 
                    known[v] = true;                // 如果找到,將頂點(diǎn)v設(shè)為已知, 
                    for (int w = 0; w < n; ++w)        // 遍歷所有v指向的頂點(diǎn)w, 
                        if (!known[w] && g[v][w] < INT_MAX && dist[w] > dist[v] + g[v][w])
                            dist[w] 
            = dist[v] + g[v][w], prev[w] = v;    // 調(diào)整頂點(diǎn)w的最短路徑長(zhǎng)dist和最短路徑的前一頂點(diǎn) prev。 
                }

            }


            void Print_SP(int v)
            {
                 
            if (v != s) Print_SP(prev[v]);
                 cout 
            << v << " ";
            }


            int main()
            {
                n 
            = 7;
                g.assign(n, vector
            <int>(n, INT_MAX));
                g[
            0][1= 2; g[0][3= 1
                g[
            1][3= 3; g[1][4= 10
                g[
            2][0= 4; g[2][5= 5
                g[
            3][2= 2; g[3][4= 2; g[3][5= 8; g[3][6= 4
                g[
            4][6= 6
                g[
            6][5= 1;
                
                s 
            = 0;
                Dijkstra();
                
                copy(dist.begin(), dist.end(), ostream_iterator
            <int>(cout, " ")); cout << endl;
                
            for (int i = 0; i < n; ++i)
                    
            if(dist[i] != INT_MAX)
                    
            {
                        cout 
            << s << "->" << i << "";
                        Print_SP(i); 
                        cout 
            << endl; 
                    }

                
                system(
            "pause");
                
            return 0;
            }



            /*============優(yōu)先隊(duì)列版================*/
            class great 
            {
            public:
                    
            bool operator() (pair<intint>& p1, pair<intint>& p2) {
                            
            return (p1.second > p2.second);
                    }

            }
            ;


            int G[N][N];

            int dijkstra(int src, int dst) {
                    vector
            <int> cost(N, INT_MAX);
                    vector
            <bool> visited(N, false);

                    priority_queue
            < pair<intint>, vector< pair<intint> >, great > Q;

                    cost[src] 
            = 0;
                    Q.push( make_pair(src, 
            0) );

                    
            while(!Q.empty()) {
                            pair
            <intint> top = Q.top();
                            Q.pop();

                            
            int v = top.first;
                            
            if (v == dst) return cost[v];

                            
            if (visited[v]) continue;
                            visited[v] 
            = true;

                            
            for(int v2 = 0; v2 < N; v2++if (G[v][v2] != 0{
                                    
            int dist = G[v][v2];
                                    
            if(cost[v2] > cost[v] + dist) {
                                            cost[v2] 
            = cost[v] + dist;
                                            Q.push( make_pair(v2, cost[v2]) );
                                    }

                            }

                    }


                    
            return -1;
            }

            久久无码中文字幕东京热| 久久久青草久久久青草| 狠狠色丁香久久婷婷综合图片| 女人高潮久久久叫人喷水| 久久精品国产清高在天天线| 国产成人精品久久亚洲高清不卡 | 精品无码久久久久久国产| 热re99久久6国产精品免费| 精品久久久久久综合日本| 久久久人妻精品无码一区| 人人狠狠综合久久88成人| 精品久久久久国产免费 | 国产精品毛片久久久久久久| 久久久久噜噜噜亚洲熟女综合| 人妻久久久一区二区三区| 国产—久久香蕉国产线看观看| 色妞色综合久久夜夜| 中文字幕久久精品| 久久国产精品无码网站| 久久久久久九九99精品| 亚洲乱码中文字幕久久孕妇黑人| 久久精品国产精品亚洲下载| 久久精品国产99国产电影网| 久久国产精品成人片免费| 久久久一本精品99久久精品88| 久久精品一区二区三区中文字幕| 久久久久久久尹人综合网亚洲| 精品国产乱码久久久久久郑州公司| 久久人与动人物a级毛片| 亚洲精品无码专区久久同性男 | 区久久AAA片69亚洲| 亚州日韩精品专区久久久| 久久一区二区三区免费| 久久亚洲2019中文字幕| 久久久久国产日韩精品网站| 久久国产热这里只有精品| 久久久艹| 国内精品久久久久久久久电影网 | 久久伊人色| 久久国内免费视频| 亚洲欧美成人综合久久久|