Question

急求最短路径算法程序，用C语言或C++

Answer 1

这是我的堆优化Dijkstra的模板：

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using std::priority_queue;
using std::vector;
using std::greater;
using std::pair;
using std::make_pair;

namespace Solve
{
const int MAX_N = 100000, MAX_M = 1000000, INF = 0x3F3F3F3F;
int n, m;
int cnt = 0, begin[MAX_N + 1], end[MAX_M + 1], next[MAX_M + 1], cost[MAX_M + 1];

typedef pair <int, int> pair_t;
priority_queue <pair_t, vector <pair_t>, greater <pair_t> > heap;

void solve(FILE *fin, FILE *fout);
void add_edge(int u, int v, int c);
int dijkstra();
}

void Solve::solve(FILE *fin, FILE *fout)
{
fscanf(fin, "%d %d", &n, &m);
for (int u, v, c; m; m--)
{
fscanf(fin, "%d %d %d", &u, &v, &c);
add_edge(u, v, c);
}
fprintf(fout, "%d\n", dijkstra());
}

void Solve::add_edge(int u, int v, int c)
{
next[++cnt] = begin[u];
begin[u] = cnt;
end[cnt] = v;
cost[cnt] = c;
}

int Solve::dijkstra()
{
int dist[MAX_N + 1];
memset(dist, 0x3F, sizeof(dist));
dist[1] = 0;
heap.push(make_pair(0, 1));

while (!heap.empty())
{
int v0 = heap.top().second;
int d0 = heap.top().first;
heap.pop();

for (int now = begin[v0], v1; now; now = next[now])
if (dist[v1 = end[now]] > d0 + cost[now])
{
dist[v1] = d0 + cost[now];
heap.push(make_pair(dist[v1], v1));
}
}

return dist[n] == INF ? -1 : dist[n];
}

int main()
{
Solve::solve(stdin, stdout);
return 0;
}

Answer 2

4． 常用算法演示程序
题目：编写常用算法的演示程序
参考：下面算法选择一种实现
矩阵旋转算法
Prim算法
拷贝链表的O(n)算法
随机算法
大数阶乘源码
格雷码算法
算术表达式的计算
寻找链表中间节点算法
模式匹配的KMP算法
最小堆/哈希表/二叉树/平衡二叉树/红黑树
最小生成树
Kruskal算法：(贪心)
最短路径Dijkstra 算法

Answer 3

这个我不是很懂，抱歉

Answer 4

y