首页 > 代码库 > Geeks : Dijkstra’s Algorithm for Adjacency List Representation 最短路径
Geeks : Dijkstra’s Algorithm for Adjacency List Representation 最短路径
最短路径的O(ElgV)的解法。
使用邻接表存储图,使用堆操作选取下一个最小路径点。
本题的难度并不在最短路径本身这个算法,而是在于堆的操作:
1 使用双重指针操作堆的节点,可以省去直接复制操作堆节点,提高效率,并且这才是有效操作动态地址数据的方法,不用双重指针,我思考了下,觉得更加不好做。
2 使用一个数组记录当前顶点在堆中的位置,相当于一个hash表了,可以需要的时候,直接从表中查找表示顶点的堆节点在堆中的位置,要记得更新节点时维护好这个表。
3 释放内存的时候注意,弹出堆的节点可以马上释放,不过注意不要双重释放内存了
记得曾经看到网上有人说堆排序是百万年薪的算法,不过现在看来光是堆排序是非常简单的算法了,会堆排序应该得达不到百万年薪吧,因为现在的算法高手应该都能随手写出堆排序的算法。
但是如本题这样灵活运用堆还是十分困难的。
参考:http://www.geeksforgeeks.org/greedy-algorithms-set-7-dijkstras-algorithm-for-adjacency-list-representation/
#include <stdio.h> #include <limits> class Dijsktra_Adjacency_List_and_Head { struct Node { int des, weight; Node *next; Node(int d, int w) : des(d), weight(w), next(NULL) {} ~Node() { if (next) delete next; next = NULL; } }; struct AdjList { Node *head; AdjList() : head(NULL) {} ~AdjList() { if (head) delete head; head = NULL; } }; struct Graph { int V; AdjList *arr; Graph(int v) : V(v) { arr = new AdjList[v]; } ~Graph() { if (arr) delete [] arr; arr = NULL; } }; void addEdge(Graph *graph, int src, int des, int wei) { Node *n = new Node(des, wei); n->next = graph->arr[src].head; graph->arr[src].head = n; n = new Node(src, wei); n->next = graph->arr[des].head; graph->arr[des].head = n; } struct heapNode { int v, dist; heapNode(int v1, int d):v(v1), dist(d){} }; struct minHeap { int size, capacity; int *pos;//记录顶点的位置 //双重指针:直接操作地址,而不是复制数据 heapNode **arr; explicit minHeap(int c = 0) : capacity(c), size(0) { pos = new int[capacity]; arr = new heapNode*[capacity];//创建存储空间 } ~minHeap() { if (pos) delete [] pos; for (int i = 0; i < size; i++) { if (arr[i]) delete arr[i], arr[i] = NULL; } if (arr) delete [] arr; } }; //双重指针的作用:这里只需要交换了地址,并不需要直接交换整个heapNode数据结构 void swapMinHeapNode(heapNode **a, heapNode **b) { heapNode *c = *a; *a = *b; *b = c; } void minheapify(minHeap *heap, int idx) { int smallest, left, right; smallest = idx; left = idx * 2 + 1; right = idx * 2 + 2;//错误+2写成+1 if (left < heap->size && heap->arr[left]->dist < heap->arr[smallest]->dist) { smallest = left; } //很难调试的bug:下面不能加else,因为要选择三种中最小的 if (right < heap->size && heap->arr[right]->dist < heap->arr[smallest]->dist) { smallest = right; } if (smallest != idx) { heapNode *smallestNode = heap->arr[smallest]; heapNode *idxNode = heap->arr[idx]; heap->pos[smallestNode->v] = idx; heap->pos[idxNode->v] = smallest; swapMinHeapNode(&heap->arr[smallest], &heap->arr[idx]); minheapify(heap, smallest); } } bool isEmpty(minHeap *heap) { return heap->size == 0; } heapNode *extraMin(minHeap *heap) { if (isEmpty(heap)) return NULL; heapNode *root = heap->arr[0]; heapNode *lastNode = heap->arr[heap->size-1]; heap->arr[0] = lastNode; //swapMinHeapNode(&root, &lastNode); heap->pos[root->v] = heap->size-1; heap->pos[lastNode->v] = 0; --heap->size; minheapify(heap, 0); return root; } void decreaseKey(minHeap *heap, int v, int dist) { int i = heap->pos[v]; heap->arr[i]->dist = dist; while (i && heap->arr[i]->dist < heap->arr[(i-1)/2]->dist) { heap->pos[heap->arr[i]->v] = (i-1)/2; heap->pos[heap->arr[(i-1)/2]->v] = i; swapMinHeapNode(&heap->arr[i], &heap->arr[(i-1)/2]); i = (i-1)/2; } } bool isInMinHeap(minHeap *heap, int v) { if (heap->pos[v] < heap->size) return true; return false; } void printArr(int dist[], int n) { printf("Vertex Distance from Source\n"); for (int i = 0; i < n; ++i) printf("%d \t\t %d\n", i, dist[i]); } void dijkstra(Graph *graph, int src, int dist[]) { int V = graph->V; minHeap *heap = new minHeap(V); for (int i = 0; i < V; i++) { dist[i] = INT_MAX; heap->arr[i] = new heapNode(i, dist[i]); heap->pos[i] = i; } dist[src] = 0; decreaseKey(heap, src, dist[src]); heap->size = V; while (!isEmpty(heap)) { heapNode *hn = extraMin(heap); int u = hn->v; delete hn; hn = NULL; Node *pCrawl = graph->arr[u].head; while (pCrawl) { int v = pCrawl->des; if (isInMinHeap(heap, v) && dist[u] != INT_MAX && pCrawl->weight + dist[u] < dist[v]) { dist[v] = pCrawl->weight + dist[u]; decreaseKey(heap, v, dist[v]); } pCrawl = pCrawl->next; } } delete heap; } public: Dijsktra_Adjacency_List_and_Head() { // create the graph given in above fugure int V = 9; struct Graph* graph = new Graph(V); addEdge(graph, 0, 1, 4); addEdge(graph, 0, 7, 8); addEdge(graph, 1, 2, 8); addEdge(graph, 1, 7, 11); addEdge(graph, 2, 3, 7); addEdge(graph, 2, 8, 2); addEdge(graph, 2, 5, 4); addEdge(graph, 3, 4, 9); addEdge(graph, 3, 5, 14); addEdge(graph, 4, 5, 10); addEdge(graph, 5, 6, 2); addEdge(graph, 6, 7, 1); addEdge(graph, 6, 8, 6); addEdge(graph, 7, 8, 7); int *dist = (int *) malloc(sizeof(int) * V); dijkstra(graph, 0, dist); printArr(dist, V); free(dist); delete graph; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。