本文共 1547 字，大约阅读时间需要 5 分钟。
此实现利用两个数组first[], ext[] 邻接表。
核心代码：
void bellman_ford(int orig) { int k; que[tail++] = orig; book[orig] = 1; while(head < tail){ k = first[que[head]]; while(k != -1){ if(dist[edge[k].v] > dist[edge[k].u] + edge[k].w){ dist[edge[k].v] = dist[edge[k].u] + edge[k].w; if(book[edge[k].v] == 0){ que[tail++] = edge[k].v; book[edge[k].v] = 1; } } k = next[k]; } book[que[head]] = 0; head++; } } #include#define INF 65535#define MAX 20typedef struct Edge{ int u, v; int w;}Edge;int que[MAX] = {0};int head = 1, tail = 1;int next[MAX+1], first[MAX+1];int book[MAX];int dist[MAX];Edge edge[MAX];void bellman_ford(int orig) { int k; que[tail++] = orig; book[orig] = 1; while(head < tail){//队列不空 就继续 k = first[que[head]];//获取 当前顶点的 ’边‘ 的 序号 while(k != -1){ if(dist[edge[k].v] > dist[edge[k].u] + edge[k].w){ dist[edge[k].v] = dist[edge[k].u] + edge[k].w; if(book[edge[k].v] == 0){ que[tail++] = edge[k].v; book[edge[k].v] = 1;//入队后 标记 } } k = next[k]; } book[que[head]] = 0;// 出队 重新把标记置 0 意味着 可以重新 入队 head++; } }int main() { int n, m; scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++ ){//初始化 book[i] = 0; first[i] = -1; next[i] = -1; dist[i] = INF; } int orig = 1; dist[orig] = 0; for(int j = 1; j <= m; j++ ){ scanf("%d%d%d", &edge[j].u,&edge[j].v, &edge[j].w); //下面两句用数组模拟链表 next[j] = first[edge[j].u]; first[edge[j].u] = j; } bellman_ford(orig); for(int i = 1; i <= n; i++ ){ printf("%d ",dist[i]); } }
转载地址：http://baimi.baihongyu.com/