斯坦福 算法2 第四周作业
斯坦福 Algorithms: Design and Analysis 2 第四周作业
来自斯坦福网站的Algorithms: Design and Analysis,与目前coursera上的版本内容没有变化,不过时间安排略有不同。
1. Problem Set 4
刚看完题目感觉有点懵。但是仔细想了一下发现这个改进算法本质上就是原来的算法没变。只不过将每次更新所有的边分成了两次进行。
感觉应该是最多的路径数量。
这个问题有些麻烦。如果没有负环,那肯定还是n-1。但是考虑到负环,那么会存在更大的情况。比如每次更新都存在一个负环,那么A[k][i][i] = A[k-1][i][k-1]+A[k-1][k-1][i]。每次都翻倍那么就是指数级别。
有环的情况,绕一圈回到自身的这条路径的权重变化为0。
2. Programming Assignment 4
给三个图的文件,得到all-pairs shortest path的最小权重。
偷懒直接实现Floyd算法:
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#include <sstream>
#include <set>
#include <string>
#include <ctime>
#include <algorithm>
using namespace std;
#define INT_MAX 2147483647
void readGraph(string fileName, unordered_map<int,int>& mp, int& size) {
cout << "read data from "<< fileName <<endl;
ifstream input(fileName);
string line;
int key, edgeSize;
int u,v,w;
input >> size >> edgeSize;
while(input >> u) {
input >> v >> w;
key = u*size+v;
mp[key] = w;
}
}
bool Floyd(const int n, unordered_map<int,int>& mp, int& res) {
vector<vector<vector<int>>> A(n+1,vector<vector<int>>(n,vector<int>(n)));
cout << "initialize Floyd matrix."<<endl;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(i == j)
A[0][i][j] = 0;
else if(mp.find((i+1)*n+j+1) != mp.end())
A[0][i][j] = mp[(i+1)*n+j+1];
else
A[0][i][j] = INT_MAX;
}
}
cout << "compute Floyd result."<<endl;
res = INT_MAX;
for(int k = 1; k <= n; k++) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(A[k-1][i][k-1] < INT_MAX && A[k-1][k-1][j] < INT_MAX)
A[k][i][j] = min(A[k-1][i][j],A[k-1][i][k-1]+A[k-1][k-1][j]); //下标从0开始的问题
else
A[k][i][j] = A[k-1][i][j];
if(i == j && A[k][i][j] < 0)
return false;
res = min(res,A[k][i][j]);
}
}
}
return true;
}
int main() {
unordered_map<int,int> mp;
int size = 0,res = 0;
string fileName1 = "g1.txt",fileName2 = "g2.txt", fileName3 = "g3.txt";
readGraph(fileName1,mp,size);
if(Floyd(size,mp,res))
cout << "result of g1: "<< res<<endl;
else
cout << "g1 has negative cycle."<<endl;
mp.clear();
readGraph(fileName2,mp,size);
if(Floyd(size,mp,res))
cout << "result of g2: "<< res<<endl;
else
cout << "g2 has negative cycle."<<endl;
mp.clear();
readGraph(fileName3,mp,size);
if(Floyd(size,mp,res))
cout << "result of g3: "<< res<<endl;
else
cout << "g3 has negative cycle."<<endl;
mp.clear();
return 0;
}
只有第三个图中没有负环。结果是-19.