首页 > 代码库 > Dijkstra 算法
Dijkstra 算法
dijkstra算法，最简单的实现需要$O(|V|^2)$。用binary heap实现，可以优化到O((|V|+|E|)lg|V|)，如果用fibonacci heap的话，可以优化到O(|E|+|V|lg|V|)。如果图是密集图的话，那这个优化效果也不好，接近$O(|V|^2)$。
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 index173 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:
6 2 3 61 3 41 2 4 62 3 54 61 3 57 9 147 10 159 10 11 215 11 66 914 2 9
每一行是顶点个数；
前几行是邻接列表；后几行是对应的边的权重；