算法系列15天速成——第十五天 图【下】（大结局）

for (int i = 0; i < g.vertexNum; i++)
            {
                //初始赋权值
                weight[i] = g.edges[vertex, i];

if (weight[i] < short.MaxValue && weight[i] > 0)
                    path[i] = vertex;

tempvertex[i] = 0;
            }

tempvertex[vertex] = 1;
            weight[vertex] = 0;

for (int i = 0; i < g.vertexNum; i++)
            {
                int min = short.MaxValue;

int index = vertex;

for (int j = 0; j < g.vertexNum; j++)
                {
                    //顶点的权值中找出最小的
                    if (tempvertex[j] == 0 && weight[j] < min)
                    {
                        min = weight[j];
                        index = j;
                    }
                }

tempvertex[index] = 1;

//以当前的index作为中间点，找出最小的权值
                for (int j = 0; j < g.vertexNum; j++)
                {
                    if (tempvertex[j] == 0 && weight[index] + g.edges[index, j] < weight[j])
                    {
                        weight[j] = weight[index] + g.edges[index, j];
                        path[j] = index;
                    }
                }
            }

Console.WriteLine("n顶点{0}到各顶点的最短路径为：（终点 < 源点） " + g.vertex[vertex]);

//最后输出
            for (int i = 0; i < g.vertexNum; i++)
            {
                if (tempvertex[i] == 1)
                {
                    var index = i;

while (index != vertex)
                    {
                        var j = index;
                        Console.Write("{0} < ", g.vertex[index]);
                        index = path[index];
                    }
                    Console.WriteLine("{0}n", g.vertex[index]);
                }
                else
                {
                    Console.WriteLine("{0} <- {1}: 无路径n", g.vertex[i], g.vertex[vertex]);
                }
            }
        }
        #endregion

最后上一下总的运行代码

复制代码 代码如下:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

（编辑：焦作站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!