Dijkstra 算法

dijkstra算法，最简单的实现需要$O(|V|^2)$。用binary heap实现，可以优化到O((|V|+|E|)lg|V|)，如果用fibonacci heap的话，可以优化到O(|E|+|V|lg|V|)。如果图是密集图的话，那这个优化效果也不好，接近$O(|V|^2)$。

fibonacci heap不涉及删除元素的操作有O(1)的平摊时间。 Extract-Min和Delete的数目和其它相比，较小时效率更佳。稠密图每次decrease key只要O(1)的平摊时间，和二项堆的O(lg n)相比是巨大的改进。

For any implementation of vertex set Q the running time is in $O(|E| cdot dk_Q + |V| cdot em_Q)$, where $dk_Q$ and $em_Q$ are times needed to perform decrease key and extract minimum operations in set Q, respectively.

The simplest implementation of the Dijkstra's algorithm stores vertices of set Q in an ordinary linked list or array, and extract minimum from Q is simply a linear search through all vertices in Q. In this case, the running time is $O(|E| + |V|^2) = O(|V|^2)$.

For sparse graphs, that is, graphs with far fewer than $O(|V|^2)$ edges, Dijkstra's algorithm can be implemented more efficiently by storing the graph in the form of adjacency lists and using a self-balancing binary search tree, binary heap, pairing heap, or Fibonacci heap as a priority queue to implement extracting minimum efficiently. With a self-balancing binary search tree or binary heap, the algorithm requires $Theta((|E| + |V|) log |V|)$ time (which is dominated by $Theta( | E | log | V | )$, assuming the graph is connected). To avoid $O(|V|)$ look-up in decrease-key step on a vanilla binary heap, it is necessary to maintain a supplementary index mapping each vertex to the heap's index (and keep it up to date as priority queue Q changes), making it take only $O(log|V|)$ time instead. The Fibonacci heap improves this to $O(|E| + |V| log|V|)$.

  1 #include <iostream>
  2 #include <string>
  3 #include <sstream>
  4 #include <fstream>
  5 #include <vector>
  6 #include <stdlib.h>
  7 #include <string.h>
  8 #include <queue>
  9 #include <map>
 10 #define MAX 10000
 11 using namespace std;
 12 
 13 struct Node {
 14     int dist;
 15     int index;
 16     Node() {}
 17     Node(int i, int d) : index(i), dist(d) {}
 18 };
 19 
 20 ostream &operator<<(ostream& os, Node& node) {
 21     os << node.index << "(" << node.dist << ") "; 
 22     return os;
 23 }
 24 
 25 class Dijkstra{
 26     public:
 27         Dijkstra():n(0), capacity(100) {
 28             this->arr = new Node[capacity];
 29         }
 30 
 31         ~Dijkstra() {
 32             delete[] arr;
 33         }
 34 
 35         void insert(Node v) {
 36             if (n >= capacity) {
 37                 Node* tmp = new Node[capacity << 1];
 38                 memcpy(tmp, arr, sizeof(Node) * capacity);
 39                 capacity <<= 1;
 40             }
 41             keyMap[v.index] = n;
 42             arr[n++] = v;
 43             shiftUp(n - 1);
 44         }
 45 
 46         void shiftDown(int st, int ed) {
 47             Node tmp = arr[st];
 48             while (st < ed) {
 49                 int next = -1;
 50                 int left = st * 2 + 1; // left child node 
 51                 if (left < ed) next = left;
 52                 else break;
 53                 int right = st * 2 + 2;
 54                 if (right < ed && arr[right].dist < arr[next].dist) next = right;
 55                 if (arr[next].dist < arr[st].dist) {
 56                     keyMap[arr[next].index] = st;
 57                     arr[st] = arr[next];
 58                     st = next;
 59                 } else break;
 60             }
 61             keyMap[tmp.index] = st;
 62             arr[st] = tmp;
 63         }
 64 
 65         void shiftUp(int ed) {
 66             Node tmp = arr[ed];
 67             while (ed > 0) {
 68                 int parent = (ed - 1) / 2;
 69                 if (arr[ed].dist < arr[parent].dist) {
 70                     keyMap[arr[parent].index] = ed;
 71                     arr[ed] = arr[parent];
 72                     ed = parent;
 73                 } else break;
 74             }
 75             keyMap[tmp.index] = ed;
 76             arr[ed] = tmp;
 77         }
 78 
 79         void update(int pos, int v) {
 80             if (pos >= n) {
 81                 arr[pos].dist = v;
 82             } else if (arr[pos].dist < v) {
 83                 arr[pos].dist = v;
 84                 shiftDown(pos, n);
 85             } else {
 86                 arr[pos].dist = v;
 87                 shiftUp(pos);
 88             }
 89         }
 90 
 91         bool empty() const {
 92             return n <= 0;
 93         }
 94 
 95         Node top() {
 96             if (empty()) return Node();
 97             return arr[0];
 98         }
 99 
100         void pop() {
101             if (empty()) return;
102             keyMap[arr[n - 1].index] = 0;
103             keyMap[arr[0].index] = n - 1;
104             swap(arr[0], arr[n - 1]);
105             shiftDown(0, --n);
106         }
107 
108         void load(string filename) {
109             ifstream in(filename.c_str());
110             string line;
111             getline(in, line);
112             int n = atoi(line.c_str());
113 
114             while (adjList.size() < n && getline(in, line)) {
115                 vector<int> neigs;
116                 stringstream ss(line);
117                 int v = 0;
118                 while (ss >> v) {
119                     neigs.push_back(v - 1);
120                 }
121                 adjList.push_back(neigs);
122             }
123 
124             while (getline(in, line)) {
125                 vector<int> ws;
126                 stringstream ss(line);
127                 int w = 0;
128                 while (ss >> w) {
129                     ws.push_back(w);
130                 }
131                 weights.push_back(ws);
132             }
133 
134             for (int i = 0; i < adjList.size(); ++i) {
135                 for (int j = 0; j < adjList[i].size(); ++j) {
136                     cout << adjList[i][j] << "(" << weights[i][j] << ") ";
137                 }
138                 cout << endl;
139             }
140         }
141 
142         // dijstra using binary heap, O((|V|+|E|)lg|V|)
143         int run() {
144             if (adjList.empty()) return 0;
145             insert(Node(0, 0));
146             for (int i = 1; i < adjList.size(); ++i) {
147                 insert(Node(i, MAX));
148             }
149 
150             while (!empty()) {    
151                 Node nearest = top(); 
152                 pop(); // O(|V|lg|V|)
153 
154                 for (int j = 0; j < adjList[nearest.index].size(); ++j) {
155                     int d = nearest.dist + weights[nearest.index][j];
156                     int neig = adjList[nearest.index][j];
157                     if (d < arr[keyMap[neig]].dist) update(keyMap[neig], d); // O(|E|lg|V|)
158                 }
159             }
160 
161             for (int i = 0; i < adjList.size(); ++i) {
162                 cout << arr[i] << " ";
163             }
164             cout << endl;
165             return 0;
166         }
167 
168     private:
169         Node* arr;
170         int n;
171         int capacity;
172         map<int, int> keyMap; // from graph index to arr index
173         vector<vector<int> > adjList, weights;
174 };
175 
176 int main()
177 {
178     Dijkstra dij;
179     dij.load("input.txt");
180     dij.run();
181     return 0;
182 }

input.txt:

每一行是顶点个数；

前几行是邻接列表；后几行是对应的边的权重；

注意

dijkstra算法是不能处理负值边和负值环的。floyd可以。
有了负值那它的，整个算法所处理的结点的顺序就有问题了。负值会使后面处理的结点到起点的权值小于已经处理了的结点到起点的权值，该算法就不适用了。
比如：
1->2 2
1->3 100
3->2 -99
用dijkstra求1开始的单源最短路的话因该会得到1->2最短路是2的错误结果。