三种最短路径算法
Dijkstra:
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef struct{
int vexs[10];
int edges[10][10];
int n;
int e;
}MGraph;
#define INFINITE 2048
void CreateGraphM(MGraph *G){
int N1,N2;
int i,j,k;
cout<<"Enter the number of vertexs and edges: "<<endl;
cin>>(G->n)>>(G->e);
k=G->n;
for(i=0;i<k;i++)
cin>>(G->vexs[i]);
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
G->edges[i][j]=-1;
cout<<"EDGES: "<<endl;
for(k=0;k<G->e;k++){
int weight;
cin>>N1>>N2>>weight;
G->edges[N1-1][N2-1]=weight;
}
return;
}
typedef struct{
int node;
int weight;
int parent;
}STORE;
bool operator< (const STORE& lhs, const STORE& rhs){
if(lhs.weight > rhs.weight)
return true;
else
return false;
}
bool FIND_STORE(const vector<STORE>& S,const STORE TMP){
for(int i=0;i<S.size();i++)
if(S[i].node == TMP.node)
return true;
return false;
}
vector<STORE> dijkstra(MGraph *G,int from){
STORE TMP;
priority_queue<STORE> Q;
vector<STORE> S;
vector<int> visited(G->n,0);
TMP.node = from;
TMP.parent = from;
TMP.weight = 0;
Q.push(TMP);
S.push_back(TMP);
while(!Q.empty()){
TMP = Q.top();
Q.pop();
for(int i=0;i<G->n;i++)
if(G->edges[TMP.node][i] > 0 && \
visited[TMP.node]==0){
STORE NEWEDGE;
NEWEDGE.node = i;
NEWEDGE.weight = G->edges[TMP.node][i] + TMP.weight;
NEWEDGE.parent = TMP.node;
Q.push(NEWEDGE);
}
visited[TMP.node] = 1;
if(!Q.empty()){
TMP = Q.top();
if(!FIND_STORE(S,TMP))
S.push_back(TMP);
}
for(int i=0;i<S.size();i++)
if(S[i].node == TMP.node){
if(TMP.weight < S[i].weight){
S[i].weight = TMP.weight;
S[i].parent = TMP.parent;
}
}
}
return S;
}
int main()
{
vector<STORE> S;
MGraph *G = new MGraph;
CreateGraphM(G);
S = dijkstra(G,0);
cout<<endl;
for(int i=0;i<S.size();i++){
cout<<S[i].node+1<<" ";
cout<<S[i].weight <<" ";
cout<<S[i].parent+1;
cout<<endl;
}
delete G;
return 0;
}
Bellman-Ford:
#include <iostream>
#include <vector>
using namespace std;
typedef struct{
int vexs[10];
int edges[10][10];
int n;
int e;
}MGraph;
#define INFINITE 2048
void CreateGraphM(MGraph *G){
int N1,N2;
int i,j,k;
cout<<"Enter the number of vertexs and edges: "<<endl;
cin>>(G->n)>>(G->e);
k=G->n;
for(i=0;i<k;i++)
cin>>(G->vexs[i]);
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
G->edges[i][j]=INFINITE;
cout<<"EDGES: "<<endl;
for(k=0;k<G->e;k++){
int weight;
cin>>N1>>N2>>weight;
G->edges[N1-1][N2-1]=weight;
}
return;
}
typedef struct{
int weight;
int parent;
}STORE;
vector<STORE> Bellman_Ford(MGraph *G,int from){
vector<STORE> S(G->n);
for(int i=0;i<G->n;i++){
S[i].weight = INFINITE;
S[i].parent = -1;
}
S[from].weight = 0;
S[from].parent = from;
for(int i=0;i<((G->n)-1);i++)
for(int j=0;j<G->n;j++)
for(int k=0;k<G->n;k++)
if(G->edges[j][k] < INFINITE){
if(S[k].weight > S[j].weight + G->edges[j][k]){
S[k].weight = S[j].weight + G->edges[j][k];
S[k].parent = j;
}
}
for(int i=0;i<G->n;i++)
for(int j=0;j<G->n;j++)
if(S[j].weight > S[i].weight + G->edges[i][j])
goto Negacyclic;
return S;
Negacyclic:
cout<<"There is Negacyclic"<<endl;
S.resize(0);
return S;
}
int main()
{
vector<STORE> S;
MGraph *G = new MGraph;
CreateGraphM(G);
S = Bellman_Ford(G,0);
cout<<endl;
for(int i=0;i<S.size();i++){
cout<<i+1<<" ";
cout<<S[i].weight <<" ";
cout<<S[i].parent+1;
cout<<endl;
}
delete G;
return 0;
}
SPFA:
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef struct{
int vexs[10];
int edges[10][10];
int n;
int e;
}MGraph;
#define INFINITE 2048
void CreateGraphM(MGraph *G){
int N1,N2;
int i,j,k;
cout<<"Enter the number of vertexs and edges: "<<endl;
cin>>(G->n)>>(G->e);
k=G->n;
for(i=0;i<k;i++)
cin>>(G->vexs[i]);
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
G->edges[i][j]=INFINITE;
cout<<"EDGES: "<<endl;
for(k=0;k<G->e;k++){
int weight;
cin>>N1>>N2>>weight;
G->edges[N1-1][N2-1]=weight;
}
return;
}
typedef struct{
int weight;
int parent;
}STORE;
vector<STORE> SPFA(MGraph *G,int from){
queue<int> Q;
vector<int> pushed(G->n,0);
vector<int> count(G->n,0);
vector<STORE> S(G->n);
for(int i=0;i<G->n;i++){
S[i].weight = INFINITE;
S[i].parent = -1;
}
S[from].weight = 0;
S[from].parent = from;
Q.push(from);
pushed[from] = 1;
while(!Q.empty()){
int cur = Q.front();
Q.pop();
count[cur]++;
if(count[cur] >= G->n)
goto Negacyclic;
pushed[cur] = 0;
for(int i=0;i<G->n;i++)
if(S[i].weight > S[cur].weight + G->edges[cur][i] && \
G->edges[cur][i] < INFINITE){
S[i].weight = S[cur].weight + G->edges[cur][i];
S[i].parent = cur;
if(pushed[i] == 0){
Q.push(i);
pushed[i]=1;
}
}
}
return S;
Negacyclic:
cout<<"There is Negacyclic"<<endl;
S.resize(0);
return S;
}
int main()
{
vector<STORE> S;
MGraph *G = new MGraph;
CreateGraphM(G);
S = SPFA(G,0);
cout<<endl;
for(int i=0;i<S.size();i++){
cout<<i+1<<" ";
cout<<S[i].weight <<" ";
cout<<S[i].parent+1;
cout<<endl;
}
delete G;
return 0;
}
分享到:
相关推荐
详细描述了解决最短路径问题的方法,包括:Dijkstra算法,Bellman-Ford算法 SPFA算法,以及一些习题。
Bellman-Ford, SPFA, Floyd : 染色法、匈牙利算法 数学知识 其他 LeetCode分类复习清单 Greedy Assignments: , Intervals: [452 Disjoint Interval], DFS / Backtracing [22 Parentheses], [46 Permutation], , [77 ...
这是我个人的技术采访资料集。 演算法 数组相关 核心 快速选择LC1471 彩虹排序 字符串匹配 核心 ... 最短路径更快算法(SPFA) LC743 在Bellman-Ford之上的改进 约翰逊算法 基数排序 联合发现LC
求单源最短路的SPFA算法的全称是:Shortest Path Faster Algorithm。...很多时候,给定的图存在负权边,这时类似Dijkstra等算法便没有了用武之地,而Bellman-Ford算法的复杂度又过高,SPFA算法便派上用场了。
Floyd,Dijkstra,bellman-ford,SPFA,A* Knuth-Morris-Pratt Boyer-Moore 参考资料 基础 《算法导论》 《Algorithms》 面试算法 《剑指offer》 《编程之美》 延伸阅读 《深入理解计算机系统》 《计算机程序的构造和...
leetcode中国 #The file is in Chinese 算法虐我千百遍,我待算法如初恋 这里的内容是我学习算法过程的一些记录,希望能一直坚持下去。...Floyd,Dijkstra,bellman-ford,spfa 排序算法 交换排序算法 冒泡排序 插入
leetcode中国 #The file is in Chinese 算法虐我千百遍,我待算法如初恋 这里的内容是我学习算法过程的一些记录,希望能一直坚持下去。...Floyd,Dijkstra,bellman-ford,spfa 排序算法 交换排序算法 冒泡排序 插入
leetcode 和 oj 算法虐我千百遍,我待算法如...Floyd,Dijkstra,bellman-ford,spfa 排序算法 交换排序算法 冒泡排序 插入排序 选择排序 希尔排序 快排 归并排序 堆排序 线性排序算法 桶排序 查找算法 顺序表查找:顺序
leetcode中国 #The file is in Chinese 算法虐我千百遍,我待算法如初恋 这里的内容是我学习算法过程的一些记录,希望能一直坚持下去。...Floyd,Dijkstra,bellman-ford,spfa 排序算法 交换排序算法 冒泡排序 插入
leetcode ...Floyd,Dijkstra,bellman-ford,spfa 排序算法 交换排序算法 冒泡排序 插入排序 选择排序 快排 堆排序 希尔排序 归并排序 线性排序算法 桶排序 查找算法 顺序表查找:顺序查找 有序表查找:二分
leetcode 和 oj 算法虐我千百遍,我待算法如...Floyd,Dijkstra,bellman-ford,spfa 排序算法 交换排序算法 冒泡排序 插入排序 选择排序 希尔排序 快排 归并排序 堆排序 线性排序算法 桶排序 查找算法 顺序表查找:顺序
leetcode算法题主函数如何写 算法虐我千百遍,我待算法...Floyd,Dijkstra,bellman-ford,spfa 排序算法 交换排序算法 冒泡排序 插入排序 选择排序 希尔排序 快排 归并排序 堆排序 线性排序算法 桶排序 查找算法 顺序表查
leetcode 和 oj 算法虐我千百遍,我待算法如...Floyd,Dijkstra,bellman-ford,spfa 排序算法 交换排序算法 冒泡排序 插入排序 选择排序 希尔排序 快排 归并排序 堆排序 线性排序算法 桶排序 查找算法 顺序表查找:顺序
leetcode 和 oj 算法虐我千百遍,我待算法如初恋 这里的内容是我学习算法过程的一些记录,希望能一直坚持...Floyd,Dijkstra,bellman-ford,spfa 排序算法 交换排序算法 冒泡排序 插入排序 选择排序 希尔排序 快排 归并排
leetcode 和 oj 算法虐我千百遍,我待算法如初恋 这里的内容是我学习算法...Floyd,Dijkstra,bellman-ford,spfa 排序算法 交换排序算法 冒泡排序 插入排序 选择排序 希尔排序 快排 归并排序 堆排序 线性排序算法 桶排序
单源最短路径(SPFA) Bellman-Ford(Queue-Optimised) 单源最短路径(Bellman-Ford) Bellman-Ford 使用Edmonds-Karp进行二分图匹配 Bigrpah-Matching(Edmonds-Karp) 普通的二叉搜索树 Binary-Search-Tree 广度...
Floyd,Dijkstra,bellman-ford,spfa 排序算法 交换排序算法 插入排序 选择排序 希尔排序 堆排序 快排 归并排序 线性排序算法基数排序 查找算法 顺序表查找:顺序查找 有序表查找:二分查找 分块...
n≤1000n≤1000 => O(n2)O(n2),O(n2logn)O(n2logn),dp,二分,朴素版Dijkstra、朴素版Prim、Bellman-Ford n≤10000n≤10000 => O(n∗n√)O(n∗n),块状链表、分块、莫队 n≤100000n≤100000 => O(nlogn)O(nlogn) =...