資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Dijkstra演算法及其鄰接表表示
給定一個圖 G(V, E) 及其鄰接表表示，並提供一個源頂點。Dijkstra 演算法用於查詢圖 G 中源頂點到任何其他頂點的最小最短路徑。
為了解決這個問題，我們將使用兩個列表。一個用於儲存已被視為最短路徑樹的頂點，另一個用於儲存尚未考慮的頂點。在演算法的每個階段，我們找到未考慮的頂點，該頂點與源的距離最小。
另一個列表用於儲存前驅節點。使用前驅節點，我們可以找到從源到目的地的路徑。
由於圖使用**鄰接表**表示，Dijkstra 最短路徑演算法的複雜度為 O(E log V)。其中 E 是邊的數量，V 是頂點的數量。
輸入和輸出
Input: The adjacency list of the graph with the cost of each edge.Output: 0 to 1, Cost: 3 Previous: 0 0 to 2, Cost: 5 Previous: 1 0 to 3, Cost: 4 Previous: 1 0 to 4, Cost: 6 Previous: 3 0 to 5, Cost: 7 Previous: 2 0 to 6, Cost: 7 Previous: 4
演算法
dijkstraShortestPath(g : Graph, dist, prev, start : node)
輸入 - 圖 g，用於儲存距離的 dist 列表，用於儲存前驅節點的 prev 列表以及起始頂點。
輸出 - 從起始頂點到所有其他頂點的最短路徑。
Begin for all vertices u in (V - start) do dist[u] := ∞ prev[u] := φ done set dist[start] = 0 and prev[start] := φ for all node u in V do insert u into queue ‘Q’. done while Q is not empty do u := minimum element from Queue delete u from Q insert u into set S for each node v adjacent with node u do if dist[u]+cost(v) < dist[v] then dist[v] := dist[u]+cost(v) prev[v] := u done done End
示例
#include<iostream>
#include<set>
#include<list>
#include<algorithm>
using namespace std;
typedef struct nodes {
int dest;
int cost;
}node;
class Graph {
int n;
list<node> *adjList;
private:
void showList(int src, list<node> lt) {
list<node> :: iterator i;
node tempNode;
for(i = lt.begin(); i != lt.end(); i++) {
tempNode = *i;
cout << "(" << src << ")---("<<tempNode.dest << "|"<<tempNode.cost<<") ";
}
cout << endl;
}
public:
Graph() {
n = 0;
}
Graph(int nodeCount) {
n = nodeCount;
adjList = new list<node>[n];
}
void addEdge(int source, int dest, int cost) {
node newNode;
newNode.dest = dest;
newNode.cost = cost;
adjList[source].push_back(newNode);
}
void displayEdges() {
for(int i = 0; i<n; i++) {
list<node> tempList = adjList[i];
showList(i, tempList);
}
}
friend void dijkstra(Graph g, int *dist, int *prev, int start);
};
void dijkstra(Graph g, int *dist, int *prev, int start) {
int n = g.n;
for(int u = 0; u<n; u++) {
dist[u] = 9999; //set as infinity
prev[u] = -1; //undefined previous
}
dist[start] = 0; //distance of start is 0
set<int> S; //create empty set S
list<int> Q;
for(int u = 0; u<n; u++) {
Q.push_back(u); //add each node into queue
}
while(!Q.empty()) {
list<int> :: iterator i;
i = min_element(Q.begin(), Q.end());
int u = *i; //the minimum element from queue
Q.remove(u);
S.insert(u); //add u in the set
list<node> :: iterator it;
for(it = g.adjList[u].begin(); it != g.adjList[u].end();it++) {
if((dist[u]+(it->cost)) < dist[it->dest]) { //relax (u,v)
dist[it->dest] = (dist[u]+(it->cost));
prev[it->dest] = u;
}
}
}
}
main() {
int n = 7;
Graph g(n);
int dist[n], prev[n];
int start = 0;
g.addEdge(0, 1, 3);
g.addEdge(0, 2, 6);
g.addEdge(1, 0, 3);
g.addEdge(1, 2, 2);
g.addEdge(1, 3, 1);
g.addEdge(2, 1, 6);
g.addEdge(2, 1, 2);
g.addEdge(2, 3, 1);
g.addEdge(2, 4, 4);
g.addEdge(2, 5, 2);
g.addEdge(3, 1, 1);
g.addEdge(3, 2, 1);
g.addEdge(3, 4, 2);
g.addEdge(3, 6, 4);
g.addEdge(4, 2, 4);
g.addEdge(4, 3, 2);
g.addEdge(4, 5, 2);
g.addEdge(4, 6, 1);
g.addEdge(5, 2, 2);
g.addEdge(5, 4, 2);
g.addEdge(5, 6, 1);
g.addEdge(6, 3, 4);
g.addEdge(6, 4, 1);
g.addEdge(6, 5, 1);
dijkstra(g, dist, prev, start);
for(int i = 0; i<n; i++)
if(i != start)
cout<<start<<" to "<<i<<", Cost: "<<dist[i]<<" Previous: "<<prev[i]<<endl;
}輸出
0 to 1, Cost: 3 Previous: 0 0 to 2, Cost: 5 Previous: 1 0 to 3, Cost: 4 Previous: 1 0 to 4, Cost: 6 Previous: 3 0 to 5, Cost: 7 Previous: 2 0 to 6, Cost: 7 Previous: 4
更新於：2020年6月15日
5K+ 次瀏覽
廣告