Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.

請問有沒有人會法則分析此題何解可以教一下嗎??

Desin a single-souce shortest path program with n vertices nonnegative direct graph.(n<30)

Input:

n m

label

lists

Output:

label distance predecessor

1 Answer

Rating
  • mkhchu
    Lv 5
    8 years ago
    Favorite Answer

    此為Single Source Shortest Paths:Label Setting 問題

    可詳見下列網址:

    http://www.csie.ntnu.edu.tw/~u91029/Path.html

    跳到有下列字眼處:

    Single Source Shortest Paths:

    Label Setting Algorithm

    以下為實作,Input及Output請自行修改:

    一點到多點的最短路徑、找出最短路徑樹(adjacency matrix)

    int w[9][9]; // 一張有權重的圖:adjacency matrix

    int d[9]; // 紀錄起點到圖上各個點的最短路徑長度

    int parent[9]; // 紀錄各個點在最短路徑樹上的父親是誰

    bool visit[9]; // 紀錄各個點是不是已在最短路徑樹之中

    void label_setting(int source)

    {

    for (int i=0; i<100; i++) visit[i] = false; // initialize

    d[source] = 0; // 設定起點的最短路徑長度

    parent[source] = source; // 設定起點是樹根(父親為自己)

    visit[source] = true; // 將起點加入到最短路徑樹

    for (int k=0; k<9-1; k++) // 將剩餘所有點加入到最短路徑樹

    {

    // 從既有的最短路徑樹,找出一條聯外而且是最短的邊

    int a = -1, b = -1, min = 1e9;

    // 找一個已在最短路徑樹上的點

    for (int i=0; i<9; i++)

    if (visit[i])

    // 找一個不在最短路徑樹上的點

    for (int j=0; j<9; j++)

    if (!visit[j])

    if (d[i] + w[i][j] < min)

    {

    a = i; // 記錄這一條邊

    b = j;

    min = d[i] + w[i][j];

    }

    // 起點有連通的最短路徑都已找完

    if (a == -1 || b == -1) break;

    // // 不連通即是最短路徑長度無限長

    // if (min == 1e9) break;

    d[b] = min; // 儲存由起點到b點的最短路徑長度

    parent[b] = a; // b點是由a點延伸過去的

    visit[b] = true; // 把b點加入到最短路徑樹之中

    }

    }

Still have questions? Get your answers by asking now.